Submission #1217123

#TimeUsernameProblemLanguageResultExecution timeMemory
1217123elotelo966Split the sequence (APIO14_sequence)C++20
71 / 100
66 ms164164 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long //#define OYY LLONG_MAX #define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); //#define fi first //#define se second #define FOR for(int i=1;i<=n;i++) //#define mid (start+end)/2 //#define pb push_back #define lim 100005 //#define N 500050 typedef long long lo; const int mod=1000000007; int n,k; lo dizi[lim],pre[lim]; lo dp[lim][2],yol[lim][205]; int q[lim]; inline bool cont(int x,int y,int cur,int cur_k){ if(dp[y][cur_k]-pre[y]*(pre[n]-pre[cur])>=dp[x][cur_k]-pre[x]*(pre[n]-pre[cur]))return 1; return 0; } inline bool cont2(int x,int y,int cur,int cur_k){ if((dp[y][cur_k]-dp[x][cur_k])*(pre[cur]-pre[y])<=(dp[cur][cur_k]-dp[y][cur_k])*(pre[y]-pre[x]))return 1; return 0; } signed main(){ faster cin>>n>>k; FOR{ cin>>dizi[i]; pre[i]=pre[i-1]+dizi[i]; } dp[0][0]=0; // 0.indeks 0.eleman alışım for(int i=1;i<=k;i++){ int l=1,r=1; q[l]=0; for(int j=1;j<=n;j++){ while(r-l>=1 && cont(q[l],q[l+1],j,0))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>=1 && cont2(q[r-1],q[r],j,0))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'; 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...