Submission #4075579
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)
//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
template < typename T >
void vprint(T &v){
REP(i, v.size()){
cout << v[i] << " ";
}
cout << endl;
}
typedef ll V;
typedef pair<V, V> pVV;
const V INF_V = INT_MAX;
const int ME = 17;
const int N = 1<<ME;
class RMQ_segtree{
public:
pVV dat[2*N-1];
RMQ_segtree(){
REP(i, 2*N-1) dat[i] = make_pair(INF_V, -1);
}
void update(int k, V a){
//k番目の要素をaに変更
k += N-1;
dat[k] = make_pair(a, k-(N-1));
while(k>0){
k = (k-1)/2;
dat[k] = min(dat[2*k+1], dat[2*k+2]);
}
}
pVV recursion(int a, int b, int k, int l, int r){
//最小値計算用の再帰関数
if(r<=a || b<=l) return make_pair(INF_V, -1);
if(a<=l && r<=b) return dat[k];
else{
pVV vl = recursion(a, b, 2*k+1, l, (l+r)/2);
pVV vr = recursion(a, b, 2*k+2, (l+r)/2, r);
return min(vl, vr);
}
}
pVV minimum(int a, int b){
//区間[a, b)の最小値
return recursion(a, b, 0, 0, N);
}
void print_val(int a, int b){
//区間[a, b)の値を出力
for(int i=a;i<b;i++) cout << dat[i+N-1].first << endl;
cout << endl;
}
};
int main(){
ll N, K;
cin >> N >> K;
vector<ll> a(N), b(N);
REP(i, N) cin >> a[i] >> b[i];
RMQ_segtree se;
REP(i, N) se.update(i, a[i]);
ll res = 0;
REP(i, K){
pVV tmp = se.minimum(0, N);
res += tmp.first;
se.update(tmp.second, tmp.first+b[tmp.second]);
}
cout << res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Factory |
User |
theory_and_me |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2036 Byte |
Status |
WA |
Exec Time |
116 ms |
Memory |
5888 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
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 |
3 ms |
4352 KB |
sample_02.txt |
AC |
18 ms |
4352 KB |
sample_03.txt |
WA |
20 ms |
4352 KB |
subtask_1_1.txt |
WA |
4 ms |
4352 KB |
subtask_1_10.txt |
AC |
51 ms |
5248 KB |
subtask_1_11.txt |
AC |
3 ms |
4352 KB |
subtask_1_12.txt |
AC |
76 ms |
5888 KB |
subtask_1_13.txt |
AC |
3 ms |
4352 KB |
subtask_1_14.txt |
AC |
32 ms |
4736 KB |
subtask_1_15.txt |
AC |
101 ms |
5888 KB |
subtask_1_16.txt |
AC |
16 ms |
4352 KB |
subtask_1_17.txt |
WA |
20 ms |
4352 KB |
subtask_1_18.txt |
AC |
116 ms |
5888 KB |
subtask_1_2.txt |
AC |
31 ms |
4480 KB |
subtask_1_3.txt |
AC |
45 ms |
5120 KB |
subtask_1_4.txt |
WA |
21 ms |
4352 KB |
subtask_1_5.txt |
AC |
88 ms |
5888 KB |
subtask_1_6.txt |
AC |
22 ms |
4352 KB |
subtask_1_7.txt |
WA |
16 ms |
4352 KB |
subtask_1_8.txt |
AC |
109 ms |
5888 KB |
subtask_1_9.txt |
AC |
102 ms |
5760 KB |