Submission #1160066

#TimeUsernameProblemLanguageResultExecution timeMemory
1160066haruki291saSplit the sequence (APIO14_sequence)C++17
100 / 100
384 ms90076 KiB
#include "bits/stdc++.h" using namespace std; using ll=long long; ll D[100003][2],S[100003]; int dq[100003],anc[100003][222]; bool vis[100003]; int n,k; bool g1(int a,int b,int c){ return (D[b][0]-D[a][0])>=(S[b]-S[a])*(S[n]-S[c]); } bool g2(int a,int b,int c){ return (D[b][0]-D[a][0])*(S[c]-S[b])<=(D[c][0]-D[b][0])*(S[b]-S[a]); } int main(){ //freopen("File","r",stdin); ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>S[i]; S[i]+=S[i-1]; } int cnt=1,pos=1; for(int i=1;i<=k;i++){ dq[cnt++]=0; for(int j=1;j<=n;j++){ while(cnt-pos>1&&g1(dq[pos],dq[pos+1],j))pos++; int idx=dq[pos]; D[j][1]=D[idx][0]+(S[j]-S[idx])*(S[n]-S[j]); anc[j][i]=idx; //dq[++cnt]=j; while(cnt-pos>1&&g2(dq[cnt-2],dq[cnt-1],j))cnt--; dq[cnt++]=j; } cnt=pos=1; for(int j=1;j<=n;j++)D[j][0]=D[j][1]; } ll ans=-1e18; int tmp=0; for(int i=1;i<=n;i++){ if(ans<D[i][0]){ ans=D[i][0]; tmp=i; } } cout<<ans<<"\n"; vector<int>pr; int t=k; while(tmp&&t>0){ vis[tmp]=true; pr.push_back(tmp); tmp=anc[tmp][t]; t--; } for(int i=1;i<n&&pr.size()<k;i++){ if(vis[i])continue; vis[i]=true; pr.push_back(i); } sort(pr.begin(),pr.end()); for(int p:pr)cout<<p<<" "; cout<<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...