#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)(1e18)
vector <int> t;
int k = 1;
void update(const int val, const int pos, int vl = 0, int vr = k - 1, int v = 0) {
if(vl == vr) {
t[v] = val;
return;
}
int vm = (vl + vr) >> 1;
if(pos <= vm) update(val, pos, vl, vm, 2*v+1);
else update(val, pos, vm+1, vr, 2*v+2);
t[v] = min(t[2*v+1], t[2*v+2]);
}
int get(int x, int vl = 0, int vr = k - 1, int v = 0) {
if(vl == vr) return vl;
else {
int vm = (vl+vr) >> 1;
if(x >= t[2*v+1]) {
return get(x, vl, vm, 2*v+1);
}else return get(x, vm+1, vr, 2*v+2);
}
}
int32_t main(void) {
int n;
cin >> n;
while(k < n) k <<= 1;
t.resize(2*k-1, inf);
vector <int> energy(n), gold(n), a(n);
for(int i = 0; i < n; i ++) {
cin >> a[i];
int ener, gol;
cin >> gol >> ener;
update((i-1<0?0:energy[i-1]) - a[i], i);
if(i == 0) energy[i] = ener;
else energy[i] = energy[i - 1] + ener;
if(i == 0) gold[i] = gol;
else gold[i] = gold[i - 1] + gol;
}
int mx = 0;
for(int i = 0; i < n; i ++) {
int ss = get(energy[i] - a[i]);
mx = max(mx, gold[i] - (ss-1<0?0:gold[ss-1]));
}
cout << mx;
return false;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
292 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
292 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
2 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
3 ms |
332 KB |
Output is correct |
| 22 |
Correct |
4 ms |
332 KB |
Output is correct |
| 23 |
Correct |
6 ms |
652 KB |
Output is correct |
| 24 |
Correct |
7 ms |
664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
292 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
2 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
3 ms |
332 KB |
Output is correct |
| 22 |
Correct |
4 ms |
332 KB |
Output is correct |
| 23 |
Correct |
6 ms |
652 KB |
Output is correct |
| 24 |
Correct |
7 ms |
664 KB |
Output is correct |
| 25 |
Correct |
5 ms |
560 KB |
Output is correct |
| 26 |
Correct |
7 ms |
908 KB |
Output is correct |
| 27 |
Correct |
9 ms |
924 KB |
Output is correct |
| 28 |
Correct |
47 ms |
2612 KB |
Output is correct |
| 29 |
Correct |
59 ms |
3764 KB |
Output is correct |
| 30 |
Correct |
120 ms |
7496 KB |
Output is correct |
| 31 |
Correct |
106 ms |
6340 KB |
Output is correct |
| 32 |
Correct |
93 ms |
6468 KB |
Output is correct |
| 33 |
Correct |
89 ms |
6312 KB |
Output is correct |
| 34 |
Correct |
88 ms |
6208 KB |
Output is correct |
| 35 |
Correct |
119 ms |
6728 KB |
Output is correct |
| 36 |
Correct |
111 ms |
6980 KB |
Output is correct |
