#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
template<class S, class T>
bool chmin(S &a, const T &b) {
return (a > b ? (a = b) == b : false);
}
template<class S, class T>
bool chmax(S &a, const T &b) {
return (a < b ? (a = b) == b : false);
}
const ll inf = 1e18;
const int mod = 1e9 + 7;
struct Segment_Tree {
int n;
vector<ll> t, modify;
Segment_Tree(int n) {
this->n = n;
t.assign(4 * n, -inf);
modify.assign(4 * n, 0);
}
void push(int v, int tl, int tr) {
t[v] += modify[v] * (tr - tl + 1);
if (tl != tr) {
modify[2 * v] += modify[v];
modify[2 * v + 1] += modify[v];
}
modify[v] = 0;
}
void upd_pos(int v, int tl, int tr, int i, ll x) {
if (tl == tr) {
t[v] = x;
return;
}
int tm = (tl + tr) >> 1;
if (tm >= i) {
upd_pos(2 * v, tl, tm, i, x);
} else {
upd_pos(2 * v + 1, tm + 1, tr, i, x);
}
t[v] = max(t[2 * v], t[2 * v + 1]);
} void upd_pos(int i, ll x) {
upd_pos(1, 0, n - 1, i, x);
}
void upd(int v, int tl, int tr, int l, int r, ll x) {
if (modify[v]) {
push(v, tl, tr);
}
if (tl > r || tr < l) {
return;
}
if (tl >= l && tr <= r) {
modify[v] += x;
push(v, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
upd(2 * v, tl, tm, l, r, x);
upd(2 * v + 1, tm + 1, tr, l, r, x);
t[v] = max(t[2 * v], t[2 * v + 1]);
} void upd(int l, int r, ll x) {
upd(1, 0, n - 1, l, r, x);
}
ll get(int v, int tl, int tr, int l, int r) {
if (modify[v]) {
push(v, tl, tr);
}
if (tl > r || tr < l) {
return -inf;
}
if (tl >= l && tr <= r) {
return t[v];
}
int tm = (tl + tr) >> 1;
return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
} int get(int i) {
int lo = i, hi = n;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (get(1, 0, n - 1, mid, n - 1) >= 0) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
};
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
ll x[n], g[n], d[n], pref[n];
for (int i = 0; i < n; ++i) {
cin >> x[i] >> g[i] >> d[i];
}
Segment_Tree t(n);
ll sum = 0;
for (int i = 0; i < n; ++i) {
sum += d[i];
t.upd_pos(i, sum - x[i] + x[0]);
pref[i] = (i == 0 ? 0 : pref[i - 1]) + g[i];
}
auto gold = [&](int l, int r) -> ll {
return pref[r] - (l == 0 ? 0 : pref[l - 1]);
};
ll res = gold(0, t.get(0));
for (int i = 1; i < n; ++i) {
t.upd(i, n - 1, x[i] - x[i - 1] - d[i - 1]);
chmax(res, gold(i, t.get(i)));
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
