Submission #19576902


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>
#include <functional>
#include <cassert>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using ld = long double;
using vld = vector<ld>;
using vb = vector<bool>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}
template <class T> ostream& operator<<(ostream& s, const vector<T>& a) { for(auto i : a) s << i << ' '; return s; }

constexpr ll INFL = 1LL << 60;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll n, k;
    cin >> n >> k;
    set<pll> st;
    vll b(n);
    rep(i, n) {
        ll a;
        cin >> a >> b[i];
        st.emplace(a, i);
    }
    ll ans = 0;
    while(k--) {
        pll p = *st.begin();
        st.erase(st.begin());
        ans += p.first;
        st.emplace(p.first + b[p.second], p.second);
    }
    cout << ans << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Submission Info

Submission Time
Task C - Factory
User Yoko_303
Language C++ (GCC 9.2.1)
Score 300
Code Size 1724 Byte
Status AC
Exec Time 93 ms
Memory 10304 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 8 ms 3480 KB
sample_02.txt AC 14 ms 3592 KB
sample_03.txt AC 10 ms 3552 KB
subtask_1_1.txt AC 2 ms 3540 KB
subtask_1_10.txt AC 41 ms 6960 KB
subtask_1_11.txt AC 4 ms 3620 KB
subtask_1_12.txt AC 63 ms 10268 KB
subtask_1_13.txt AC 2 ms 3592 KB
subtask_1_14.txt AC 30 ms 5384 KB
subtask_1_15.txt AC 77 ms 10196 KB
subtask_1_16.txt AC 8 ms 3536 KB
subtask_1_17.txt AC 11 ms 3528 KB
subtask_1_18.txt AC 71 ms 10304 KB
subtask_1_2.txt AC 29 ms 4216 KB
subtask_1_3.txt AC 34 ms 6628 KB
subtask_1_4.txt AC 27 ms 3664 KB
subtask_1_5.txt AC 63 ms 10252 KB
subtask_1_6.txt AC 20 ms 3896 KB
subtask_1_7.txt AC 13 ms 3604 KB
subtask_1_8.txt AC 93 ms 10196 KB
subtask_1_9.txt AC 79 ms 9420 KB