Submission #46620

#TimeUsernameProblemLanguageResultExecution timeMemory
46620dqhungdlSplit the sequence (APIO14_sequence)C++17
71 / 100
2051 ms85608 KiB
#include <bits/stdc++.h> using namespace std; struct Data { int64_t a,b; int id; }; typedef pair<int64_t,int64_t> ii; int n,k,top,pointer,Trace[100005][205]; int64_t a[100005],f[100005],ff[100005]; Data S[100005]; bool Check(Data x1,Data x2,Data x3) { ///Intersection(x1,x2)=(x1.b-x2.b)/(x2.a-x1.a) ///Intersection(x1,x3)=(x1.b-x3.b)/(x3.a-x1.a) return (x1.b-x3.b)*(x2.a-x1.a)<=(x1.b-x2.b)*(x3.a-x1.a); } void Update(int64_t x,int64_t y,int id) { while(top>=2&&Check(S[top-1],S[top],{x,y,id})==true) top--; S[++top]={x,y,id}; } ii Query(int64_t x) { pointer=min(pointer,top); while(pointer<top&&S[pointer+1].a*x+S[pointer+1].b<=S[pointer].a*x+S[pointer].b) pointer++; return ii(S[pointer].a*x+S[pointer].b,S[pointer].id); } void Process(int kk) { top=0; pointer=1; Update(0,0,0); for(int i=1;i<=n;i++) { ii tmp=Query(a[i]); ff[i]=-tmp.first; Trace[i][kk]=tmp.second; Update(-a[i],a[i]*a[i]-f[i],i); } for(int i=1;i<=n;i++) f[i]=ff[i]; } int main() { //ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]+=a[i-1]; } for(int i=1;i<=k;i++) Process(i); cout<<f[n]<<"\n"; while(k>0) { n=Trace[n][k]; k--; cout<<n<<' '; } }
#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...