#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long inf = 1e18;
int n;
long long x[N], g[N], d[N];
long long T[N];
long long ans;
vector<long long> z; // for compression
void upd(int x, long long val) { for(; x < N; x += x & -x) T[x] = min(T[x], val); }
long long get(int x) { long long res = inf; for (; x > 0; x -= x & -x) res = min(res, T[x]); return res; }
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> g[i] >> d[i]; // (coordinate, gold, energy)
d[i] += d[i-1];
g[i] += g[i-1];
}
for (int i = 1; i <= n; ++i) {
// compress all values
z.push_back(d[i] - x[i]);
z.push_back(d[i-1] - x[i]);
}
sort(z.begin(), z.end());
z.resize(distance(z.begin(), unique(z.begin(), z.end())));
for (int i = 0; i < N; ++i) T[i] = inf;
for (int i = 1; i <= n; ++i) {
int pos = lower_bound(z.begin(), z.end(), d[i-1] - x[i]) - z.begin() + 1;
upd(pos, g[i-1]); // update to BIT
pos = lower_bound(z.begin(), z.end(), d[i] - x[i]) - z.begin() + 1;
long long cur = g[i] - get(pos);
ans = max(ans, cur); // update to answer
}
cout << ans << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 5 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 6 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 7 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 8 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 9 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 10 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 11 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 12 |
Correct |
0 ms |
8424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 5 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 6 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 7 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 8 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 9 |
Correct |
3 ms |
8424 KB |
Output is correct |
| 10 |
Correct |
0 ms |
8424 KB |
Output is correct |
| 11 |
Correct |
3 ms |
8584 KB |
Output is correct |
| 12 |
Correct |
3 ms |
8584 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8584 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8844 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8844 KB |
Output is correct |
| 4 |
Correct |
26 ms |
10000 KB |
Output is correct |
| 5 |
Correct |
36 ms |
10000 KB |
Output is correct |
| 6 |
Correct |
56 ms |
11536 KB |
Output is correct |
| 7 |
Correct |
49 ms |
11536 KB |
Output is correct |
| 8 |
Correct |
59 ms |
11536 KB |
Output is correct |
| 9 |
Correct |
69 ms |
11536 KB |
Output is correct |
| 10 |
Correct |
59 ms |
11536 KB |
Output is correct |
| 11 |
Correct |
63 ms |
11536 KB |
Output is correct |
| 12 |
Correct |
53 ms |
11536 KB |
Output is correct |
