Submission #1216981

#TimeUsernameProblemLanguageResultExecution timeMemory
1216981elotelo966Split the sequence (APIO14_sequence)C++20
0 / 100
0 ms328 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; int dizi[lim],pre[lim]; int dp[lim][205],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; } int32_t 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,i-1))l++; dp[j][i]=dp[q[l]][i-1]+(pre[j]-pre[q[l]])*(pre[n]-pre[j]); yol[j][i]=q[l]; while(r-l>=1 && cont2(q[r],q[r-1],j,i-1))r--; q[++r]=j; } } int cev=LLONG_MIN,bas=0; FOR{ if(cev<dp[i][k]){ cev=dp[i][k]; bas=i; } } vector<int> ans; for(int i=k;i>=1;i--){ ans.pb(bas); bas=yol[bas][i]; } cout<<cev<<'\n'; reverse(ans.begin(),ans.end()); for(auto a:ans){ cout<<a<<" "; } 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...