Submission #5396

#TimeUsernameProblemLanguageResultExecution timeMemory
5396gs12117Divide and conquer (IZhO14_divide)C++98
100 / 100
68 ms6952 KiB
#include<stdio.h> #include<algorithm> int n; int x[100100]; int gold[100100]; long long int gsum[100100]; int eng[100100]; long long int esum[100100]; struct data{ long long int gtot; long long int etot; bool operator<(const data &r)const{ return etot<r.etot||(etot==r.etot&&gtot<r.gtot); } }; data points[200100]; long long int ans; int main(){ int i; long long int ming; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d%d%d",&x[i],&gold[i],&eng[i]); gsum[i+1]=gold[i]+gsum[i]; esum[i+1]=eng[i]+esum[i]; } for(i=0;i<n;i++){ points[i*2].gtot=gsum[i]; points[i*2].etot=esum[i]-x[i]; points[i*2+1].gtot=gsum[i+1]; points[i*2+1].etot=esum[i+1]-x[i]; } std::sort(points,points+2*n); ming=points[0].gtot; for(i=1;i<2*n;i++){ if(ming>points[i].gtot)ming=points[i].gtot; if(ans<points[i].gtot-ming)ans=points[i].gtot-ming; } printf("%lld",ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...