#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline int in() {
int result = 0;
char ch = getchar_unlocked();
while (true) {
if(ch >= '0' && ch <= '9')
break;
ch = getchar_unlocked();
}
result = ch-'0';
while(true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result*10 + (ch - '0');
}
return result;
}
inline void out(ll x) {
ll rev=x;
int count = 0;
while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
rev = 0;
while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
while(count--)
putchar_unlocked('0');
}
const int mxN=1e5;
int n, x[mxN];
ll pg[mxN+1], pd[mxN+1], pts[mxN], ft[mxN+1], ans;
inline void upd(int i, ll x) {
for(++i; i<=n; i+=i&-i)
ft[i]=max(x, ft[i]);
}
inline ll qry(int i) {
ll r=0;
for(; i; i-=i&-i)
r=max(ft[i], r);
return r;
}
int main() {
n=in();
for(int i=0; i<n; ++i) {
x[i]=in(), pg[i+1]=in()+pg[i], pd[i+1]=in()+pd[i];
pts[i]=x[i]-pd[i+1];
}
sort(pts, pts+n);
for(int i=n-1; i>=0; --i) {
upd(lower_bound(pts, pts+n, x[i]-pd[i+1])-pts, pg[i+1]);
ans=max(qry(upper_bound(pts, pts+n, x[i]-pd[i])-pts)-pg[i], ans);
}
out(ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
11 ms |
492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
672 KB |
Output is correct |
| 8 |
Correct |
2 ms |
672 KB |
Output is correct |
| 9 |
Correct |
2 ms |
672 KB |
Output is correct |
| 10 |
Correct |
2 ms |
672 KB |
Output is correct |
| 11 |
Correct |
2 ms |
672 KB |
Output is correct |
| 12 |
Correct |
3 ms |
744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
744 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
760 KB |
Output is correct |
| 4 |
Correct |
3 ms |
760 KB |
Output is correct |
| 5 |
Correct |
3 ms |
760 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
760 KB |
Output is correct |
| 9 |
Correct |
3 ms |
760 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Correct |
3 ms |
764 KB |
Output is correct |
| 12 |
Correct |
4 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
768 KB |
Output is correct |
| 2 |
Correct |
4 ms |
896 KB |
Output is correct |
| 3 |
Correct |
4 ms |
896 KB |
Output is correct |
| 4 |
Correct |
15 ms |
2300 KB |
Output is correct |
| 5 |
Correct |
16 ms |
2356 KB |
Output is correct |
| 6 |
Correct |
31 ms |
4092 KB |
Output is correct |
| 7 |
Correct |
27 ms |
4092 KB |
Output is correct |
| 8 |
Correct |
28 ms |
4096 KB |
Output is correct |
| 9 |
Correct |
29 ms |
4096 KB |
Output is correct |
| 10 |
Correct |
30 ms |
4096 KB |
Output is correct |
| 11 |
Correct |
38 ms |
4096 KB |
Output is correct |
| 12 |
Correct |
33 ms |
4096 KB |
Output is correct |
