Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<queue>
- #include<stack>
- #include<deque>
- #include<vector>
- #include<string>
- using namespace std;
- #define INF 1000000000
- #define lint long long
- #define pb push_back
- #define mp make_pair
- #define MOD 1000000007
- pair <int,pair<int,int> > a[100005];
- lint p[100005],mx[100005],d[100005];
- int n;
- int check(lint g)
- {
- int i,j=n,k;
- lint gsum=0,esum,enc,enn;
- for(i=n;i>0;--i)
- {
- gsum+=a[i].second.first;
- while(1)
- {
- if(gsum-a[j].second.first<g)break;
- gsum-=a[j].second.first;
- --j;
- }
- if(gsum<g)continue;
- enc=p[j]-p[i-1]+(a[i].first-a[i-1].first);
- enn=mx[j]-p[j];
- if(enn+enc>=0)return 1;
- }
- return 0;
- }
- int main()
- {
- int i,j;
- lint l=0,r=1;
- scanf("%d",&n);
- p[0]=0;
- for(i=1;i<=n;++i)
- {
- scanf("%d %d %d",&a[i].first,&a[i].second.first,&a[i].second.second);
- d[i]=d[i-1]+a[i].first;
- p[i]=p[i-1]+a[i].second.second+a[i-1].first-a[i].first;
- r+=a[i].second.first;
- }
- p[n+1]=INF*1ll*INF;
- mx[n]=p[n];
- for(i=n-1;i>0;--i)
- {
- mx[i]=max(p[i],mx[i+1]);
- }
- while(r-l>1)
- {
- lint mid=(r+l)/2;
- if(check(mid))
- l=mid;
- else r=mid;
- }
- if(check(r))l=r;
- printf("%lld",l);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement