제출 #68435

#제출 시각아이디문제언어결과실행 시간메모리
68435tatatan금 캐기 (IZhO14_divide)C++11
100 / 100
55 ms3712 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define pii pair<int,int> #define LL long long #define st first #define nd second #define endl '\n' using namespace std; const int MAXN=100005; LL f[MAXN*4],lz[MAXN*4],n,x[MAXN],g[MAXN],d[MAXN],p[MAXN],ans; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;++i) { cin>>x[i]>>g[i]>>d[i]; d[i]+=d[i-1]; g[i]+=g[i-1]; } for(int i=n;i>=1;--i) { if(i==n) p[i]=d[i]-x[i]; else p[i]=max(p[i+1],d[i]-x[i]); } for(int i=1;i<=n;++i) { int l=i,r=n+1,md; while(l+1<r) { md=(l+r)/2; if(p[md]>=d[i-1]-x[i]) l=md; else r=md; } ans=max(ans,g[l]-g[i-1]); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...