#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
long long a[n+2],b[n+1],c[n+1],d[n+1],f[n+1],g[n+1];
int h[n+1];
for(int i=0;i<n;i++)
{
cin >> a[i+1] >> b[i+1] >> c[i+1];
}
a[n+1]=a[n];a[0]=0;b[0]=0;c[0]=a[1]-a[0];d[0]=c[0];g[0]=0;f[0]=0;
for(int i=1;i<=n;i++)
{
g[i]=g[i-1]+b[i];
d[i]=c[i]+d[i-1];
f[i]=d[i]-a[i+1];
}
vector<pair<long long,int> > v;
for(int i=0;i<=n;i++)
{
v.push_back({f[i],i});
}
sort(v.begin(),v.end());/*
for(int i=0;i<=n;i++)
{
cout << v[i].first << ' ' << v[i].second << '\n';
}
cout << endl;
/**/
long long res=0;
h[0]=v[0].second;
for(int i=1;i<=n;i++) h[i]=min(h[i-1],v[i].second);
for(int i=0;i<=n;i++)
{
long long x=v[i].first+a[v[i].second+1]-a[v[i].second];
//cout << x << ' ' ;
int l=0,r=i-1,ans=1000000000;
while(l<=r)
{
int g=(l+r)/2;
if(v[g].first<=x)
{
ans=min(ans,h[g]);
l=g+1;
}
else r=g-1;
}
l=i+1;r=n;
while(l<=r)
{
int g=(l+r)/2;
if(v[g].first<=x)
{
ans=min(ans,h[g]);
l=g+1;
}
else r=g-1;
}
//cout << ans << '\n';
if(ans>n||ans>v[i].second)
{
continue;
}
res=max(res,g[v[i].second]-g[ans]);
}
cout << res;
return 0;
}
/*
2
0 4 1
3 5 1
2
1 4 2
3 5 0
*/
Compilation message
divide.cpp:32:2: warning: "/*" within comment [-Wcomment]
32 | /**/
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
3 ms |
788 KB |
Output is correct |
| 24 |
Correct |
3 ms |
860 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
3 ms |
788 KB |
Output is correct |
| 24 |
Correct |
3 ms |
860 KB |
Output is correct |
| 25 |
Correct |
2 ms |
860 KB |
Output is correct |
| 26 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 27 |
Correct |
5 ms |
1416 KB |
Output is correct |
| 28 |
Correct |
25 ms |
5112 KB |
Output is correct |
| 29 |
Correct |
31 ms |
5332 KB |
Output is correct |
| 30 |
Correct |
64 ms |
10348 KB |
Output is correct |
| 31 |
Correct |
47 ms |
9416 KB |
Output is correct |
| 32 |
Correct |
51 ms |
9448 KB |
Output is correct |
| 33 |
Correct |
48 ms |
9156 KB |
Output is correct |
| 34 |
Correct |
48 ms |
9412 KB |
Output is correct |
| 35 |
Correct |
53 ms |
9824 KB |
Output is correct |
| 36 |
Correct |
67 ms |
9928 KB |
Output is correct |
