#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200'010;
struct obj { ll x, g, e, gm, em; } a[N], b[N];
int n;
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop (i,0,n)
cin >> a[i].x >> a[i].g >> a[i].e;
Loop (i,1,n) {
a[i].gm = a[i-1].g;
a[i].em = a[i-1].e;
a[i].g += a[i].gm;
a[i].e += a[i].em;
}
Loop (i,0,n) {
a[i].e -= a[i].x;
a[i].em -= a[i].x;
}
memcpy(b, a, sizeof(b));
sort(a, a+n, [](obj &x, obj &y){return x.e < y.e;});
sort(b, b+n, [](obj &x, obj &y){return x.em < y.em;});
ll ans = 0;
ll mn = 1e18;
for (int i=0, j=0; i < n; ++i) {
while (j < n && b[j].em <= a[i].e) {
mn = min(mn, b[j].gm);
++j;
}
ans = max(ans, a[i].g - mn);
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8136 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8124 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8144 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 11 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 12 |
Correct |
6 ms |
8148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8136 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8124 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8144 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 11 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 12 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 13 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 14 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 15 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 16 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 17 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 19 |
Correct |
4 ms |
8156 KB |
Output is correct |
| 20 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 21 |
Correct |
5 ms |
8144 KB |
Output is correct |
| 22 |
Correct |
5 ms |
8280 KB |
Output is correct |
| 23 |
Correct |
5 ms |
8404 KB |
Output is correct |
| 24 |
Correct |
6 ms |
8404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8136 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8124 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8144 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 11 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 12 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 13 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 14 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 15 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 16 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 17 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 19 |
Correct |
4 ms |
8156 KB |
Output is correct |
| 20 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 21 |
Correct |
5 ms |
8144 KB |
Output is correct |
| 22 |
Correct |
5 ms |
8280 KB |
Output is correct |
| 23 |
Correct |
5 ms |
8404 KB |
Output is correct |
| 24 |
Correct |
6 ms |
8404 KB |
Output is correct |
| 25 |
Correct |
8 ms |
8396 KB |
Output is correct |
| 26 |
Correct |
8 ms |
8680 KB |
Output is correct |
| 27 |
Correct |
8 ms |
8660 KB |
Output is correct |
| 28 |
Correct |
20 ms |
11128 KB |
Output is correct |
| 29 |
Correct |
24 ms |
11332 KB |
Output is correct |
| 30 |
Correct |
38 ms |
14940 KB |
Output is correct |
| 31 |
Correct |
32 ms |
13772 KB |
Output is correct |
| 32 |
Correct |
32 ms |
13784 KB |
Output is correct |
| 33 |
Correct |
33 ms |
13692 KB |
Output is correct |
| 34 |
Correct |
35 ms |
13632 KB |
Output is correct |
| 35 |
Correct |
46 ms |
14208 KB |
Output is correct |
| 36 |
Correct |
35 ms |
14284 KB |
Output is correct |
