#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
vector<int> t;
int getmin(int v, int tl, int tr, int l, int r) {
if (tl > tr || l > r) return 1e15;
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) >> 1;
return min(getmin(2 * v, tl, tm, l, min(r, tm)), getmin(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
void upd(int v, int tl, int tr, int x, int pos) {
if (tl == tr) {
t[v] = min(t[v], x);
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm) {
upd(2 * v, tl, tm, x, pos);
}
else upd(2 * v + 1, tm + 1, tr, x, pos);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
int32_t main() {
fstream cin("divide.in");
ofstream cout("divide.out");
int n;
cin >> n;
vector<vector<int>> a;
for (int i = 0; i < n; ++i) {
int x, g, e;
cin >> x >> g >> e;
a.push_back({ x,g,e });
}
vector<int> pr(n + 1);
for (int i = 0; i < n; ++i) {
pr[i + 1] = pr[i] + a[i][2];
}
vector<int> pr_gold(n + 1);
for (int i = 0; i < n; ++i) {
pr_gold[i + 1] = pr_gold[i] + a[i][1];
}
vector<int> coord;
for (int i = 0; i < n; ++i) {
coord.push_back(pr[i] - a[i][0]);
coord.push_back(pr[i + 1] - a[i][0]);
}
sort(coord.begin(), coord.end());
int N = coord.size();
t.resize(4 * N, 1e15);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (i == 0) {
int pos = lower_bound(coord.begin(), coord.end(), pr[i] - a[i][0]) - coord.begin();
upd(1, 0, N - 1, pr_gold[i], pos);
}
else {
int pos = lower_bound(coord.begin(), coord.end(), pr[i + 1] - a[i][0]) - coord.begin();
int x = getmin(1, 0, N - 1, 0, pos);
ans = max(ans, pr_gold[i + 1] - x);
ans = max(ans, a[i][1]);
}
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
