#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = (1<<18);
int tree[2*maxn];
void update(int k, int v) {
for (int i = k+maxn; i >= 1; i /= 2) tree[i] = min(tree[i], v);
}
int query(int l, int r) {
l += maxn, r += maxn;
int res = 1e18;
while (l <= r) {
if (l%2==1) res = min(res, tree[l++]);
if (r%2==0) res = min(res, tree[r--]);
l /= 2, r /= 2;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 2*maxn; i++) tree[i] = 1e18;
int n;
cin >> n;
int x[n+1], g[n+1], e[n+1];
x[0] = g[0] = e[0] = 0;
set<int> s;
for (int i = 1; i <= n; i++) {
int xi, gi, ei;
cin >> xi >> gi >> ei;
x[i] = xi;
g[i] = g[i-1] + gi;
e[i] = e[i-1] + ei;
s.insert(x[i]-e[i-1]);
s.insert(x[i]-e[i]);
}
vector<int> v(s.begin(), s.end());
map<int,int> m;
for (int i = 0; i < v.size(); i++) m[v[i]] = i;
int best = 0;
for (int r = 1; r <= n; r++) {
update(m[x[r]-e[r-1]], g[r-1]);
int res = g[r]-query(m[x[r]-e[r]], maxn-1);
best = max(best, res);
}
cout << best << '\n';
}
Compilation message
divide.cpp: In function 'int main()':
divide.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < v.size(); i++) m[v[i]] = i;
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4480 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4480 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4480 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4608 KB |
Output is correct |
| 16 |
Correct |
4 ms |
4608 KB |
Output is correct |
| 17 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 19 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4736 KB |
Output is correct |
| 21 |
Correct |
5 ms |
4864 KB |
Output is correct |
| 22 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 23 |
Correct |
12 ms |
5888 KB |
Output is correct |
| 24 |
Correct |
10 ms |
5888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4480 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4480 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4480 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4608 KB |
Output is correct |
| 16 |
Correct |
4 ms |
4608 KB |
Output is correct |
| 17 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 19 |
Correct |
4 ms |
4736 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4736 KB |
Output is correct |
| 21 |
Correct |
5 ms |
4864 KB |
Output is correct |
| 22 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 23 |
Correct |
12 ms |
5888 KB |
Output is correct |
| 24 |
Correct |
10 ms |
5888 KB |
Output is correct |
| 25 |
Correct |
9 ms |
5760 KB |
Output is correct |
| 26 |
Correct |
20 ms |
7168 KB |
Output is correct |
| 27 |
Correct |
20 ms |
7168 KB |
Output is correct |
| 28 |
Correct |
81 ms |
18424 KB |
Output is correct |
| 29 |
Correct |
86 ms |
18680 KB |
Output is correct |
| 30 |
Correct |
189 ms |
33144 KB |
Output is correct |
| 31 |
Correct |
174 ms |
32120 KB |
Output is correct |
| 32 |
Correct |
167 ms |
32120 KB |
Output is correct |
| 33 |
Correct |
148 ms |
31936 KB |
Output is correct |
| 34 |
Correct |
151 ms |
31096 KB |
Output is correct |
| 35 |
Correct |
155 ms |
32376 KB |
Output is correct |
| 36 |
Correct |
151 ms |
32760 KB |
Output is correct |
