Submission #19576941


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;
    priority_queue<pll, vpll, greater<pll>> que;
    vll b(n);
    rep(i, n) {
        ll a;
        cin >> a >> b[i];
        que.emplace(a, i);
    }
    ll ans = 0;
    while(k--) {
        pll p = que.top();
        que.pop();
        ans += p.first;
        que.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 1745 Byte
Status AC
Exec Time 47 ms
Memory 6064 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 9 ms 3460 KB
sample_02.txt AC 8 ms 3556 KB
sample_03.txt AC 3 ms 3464 KB
subtask_1_1.txt AC 2 ms 3460 KB
subtask_1_10.txt AC 27 ms 4560 KB
subtask_1_11.txt AC 3 ms 3588 KB
subtask_1_12.txt AC 32 ms 5988 KB
subtask_1_13.txt AC 4 ms 3588 KB
subtask_1_14.txt AC 17 ms 3992 KB
subtask_1_15.txt AC 44 ms 5900 KB
subtask_1_16.txt AC 5 ms 3604 KB
subtask_1_17.txt AC 3 ms 3620 KB
subtask_1_18.txt AC 40 ms 6064 KB
subtask_1_2.txt AC 19 ms 3816 KB
subtask_1_3.txt AC 17 ms 4564 KB
subtask_1_4.txt AC 19 ms 3576 KB
subtask_1_5.txt AC 31 ms 5992 KB
subtask_1_6.txt AC 16 ms 3704 KB
subtask_1_7.txt AC 9 ms 3600 KB
subtask_1_8.txt AC 47 ms 5928 KB
subtask_1_9.txt AC 42 ms 5896 KB