Submission #1217141

#TimeUsernameProblemLanguageResultExecution timeMemory
1217141elotelo966Split the sequence (APIO14_sequence)C++20
71 / 100
69 ms161808 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define FOR for(int i=1;i<=n;i++) const int lim=100002; typedef long long lo; int n,k; lo dizi[lim],pre[lim]; lo dp[lim][2],yol[lim][202]; int q[lim]; inline bool cont(int x,int y,int cur){ if(dp[y][0]-pre[y]*(pre[n]-pre[cur])>=dp[x][0]-pre[x]*(pre[n]-pre[cur]))return 1; return 0; } inline bool cont2(int x,int y,int cur){ if((dp[y][0]-dp[x][0])*(pre[cur]-pre[y])<=(dp[cur][0]-dp[y][0])*(pre[y]-pre[x]))return 1; return 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>k; FOR{ cin>>dizi[i]; pre[i]=pre[i-1]+dizi[i]; } int l,r; for(int i=1;i<=k;i++){ l=1,r=1; q[l]=0; for(int j=1;j<=n;j++){ while(r-l>0 && cont(q[l],q[l+1],j))l++; dp[j][1]=dp[q[l]][0]+(pre[j]-pre[q[l]])*(pre[n]-pre[j]); yol[j][i]=q[l]; while(r-l>0 && cont2(q[r-1],q[r],j))r--; q[++r]=j; } for(int j=1;j<=n;j++){ dp[j][0]=dp[j][1]; } } lo cev=-5; int bas=0; for(int i=n-1;i>=1;i--){ if(cev<dp[i][0]){ cev=dp[i][0]; bas=i; } } cout<<cev<<'\n'; for(int i=k;i>=1;i--){ cout<<bas<<" "; bas=yol[bas][i]; } 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...