제출 #1217116

#제출 시각아이디문제언어결과실행 시간메모리
1217116elotelo966Split the sequence (APIO14_sequence)C++20
71 / 100
66 ms164420 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][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; } 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,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; } //~ cout<<"begin"<<" "<<i<<endl; //~ for(int j=l;j<=r;j++)cout<<q[j]<<" "; //~ cout<<endl; for(int j=1;j<=n;j++){ dp[j][0]=dp[j][1]; } } //~ FOR{ //~ for(int j=1;j<=k;j++){ //~ cout<<dp[i][j]<<" "; //~ } //~ cout<<endl; //~ } int cev=LLONG_MIN,bas=0; FOR{ if(cev<dp[i][0]){ cev=dp[i][0]; 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...