Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define llong long long
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- using namespace std;
- const int INF = (int) 1e9 + 7;
- const int MXN = (int) 2e5 + 7;
- struct node {
- int pos, g, e;
- };
- int n;
- int smax[MXN];
- llong ans;
- llong sg[MXN], se[MXN];
- node a[MXN];
- pair<llong, int> all[MXN];
- int main() {
- freopen("divide.in", "r", stdin);
- freopen("divide.out", "w", stdout);
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- scanf("%d%d%d", &a[i].pos, &a[i].g, &a[i].e);
- sg[i] = sg[i - 1] + a[i].g;
- se[i] = se[i - 1] + a[i].e;
- all[i] = mp(se[i] - a[i].pos, i);
- }
- sort(all + 1, all + n + 1);
- for (int i = n; i >= 1; i--)
- smax[i] = max(smax[i + 1], all[i].S);
- for (int i = 1; i <= n; i++) {
- int low = lower_bound(all + 1, all + n + 1, mp(se[i - 1] - a[i].pos, 0)) - all;
- int nxt = smax[low];
- ans = max(ans, sg[nxt] - sg[i - 1]);
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment