Submission #731525

#TimeUsernameProblemLanguageResultExecution timeMemory
731525mohav48173Feast (NOI19_feast)C++14
63 / 100
1079 ms5096 KiB
#include<bits/stdc++.h> using namespace std; int n,k; const long double sz=1e-6; long long a[400000]; long long m[400000]; long long mincnt=0; long double score=0; long double get(int ind) { if(ind<0)return 0; else return m[ind]; } void calc(long double lam) { long double bestscore=0; long long bestcnt=0; long double bestnxt=-lam; long long nxtcnt=0; for(int i=0;i<n;i++) { if(bestscore-lam-get(i-1)>bestnxt || (bestscore-lam-get(i-1)==bestnxt && nxtcnt>bestcnt)) { bestnxt=bestscore-get(i-1)-lam; nxtcnt=bestcnt; } if(bestnxt+get(i)>bestscore || (bestnxt+get(i)==bestscore && nxtcnt+1<bestcnt)) { bestscore=bestnxt+get(i); bestcnt=nxtcnt+1; } } mincnt=bestcnt; score=bestscore; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; m[0]=a[0];for(int i=1;i<n;i++)m[i]=m[i-1]+a[i]; long double l=0,r=1e16; while(l+sz<r) { long double mid=(l+r)/2.0; calc(mid); if(mincnt<k)r=mid; else l=mid; } calc(r); cout<<(long long)(round(score+k*r))<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...