| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 737837 | amirhoseinfar1385 | Split the sequence (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<vector<long long>>dp;
vector<vector<int>>dpa;
vector<long long>ps,suf;
int n,k;
void solve(int l,int r,int tl,int tr,int fj){
//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<fj<<endl;
if(l>r||tl>tr){
return ;
}
if(tl==tr){
for(int i=l;i<=r;i++){
dpa[i][fj]=tl;
}
return ;
}
int mid=(l+r)>>1;
for(int i=tl;i<=min(tr,mid-1);i++){
long long fake=dp[i][fj-1]+(ps[mid]-ps[i])*suf[mid+1];
if(fake>dp[mid][fj]){
dp[mid][fj]=fake;
dpa[mid][fj]=i;
}
}
solve(l,mid-1,tl,dpa[mid][fj],fj);
solve(mid+1,r,dpa[mid][fj],tr,fj);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
vector<long long>all(n+1);
for(int i=1;i<=n;i++){
cin>>all[i];
}
dp.resize(n+3,vector<long long>(k+5));
dpa.resize(n+3,vector<long long>(k+5));
ps.resize(n+3);
suf.resize(n+3);
for(int i=1;i<=n;i++){
ps[i]=ps[i-1]+all[i];
}
for(int i=n;i>=1;i--){
suf[i]=all[i]+suf[i+1];
}
for(int i=1;i<=n;i++){
dp[i][1]=ps[i]*suf[i+1];
dpa[i][1]=-1;
}
for(int j=2;j<=k;j++){
solve(j,n,1,n,j);
for(int i=1;i<j;i++){
dp[i][j]=dp[i][j-1];
dpa[i][j]=dpa[i][j-1];
}
for(int i=j;i<=n;i++){
dp[i][j]=dp[dpa[i][j]][j-1]+(ps[i]-ps[dpa[i][j]])*suf[i+1];
}
}
long long maxa=-1,w=0;
for(int i=1;i<n;i++){
if(dp[i][k]>maxa){
w=i;
maxa=dp[i][k];
}
}
cout<<maxa<<"\n";
int now=k;
vector<int>res;
vector<int>vis(n+3);
while(now>0&&w>0){
//cout<<now<<" "<<w<<endl;
res.push_back(w);
vis[w]=1;
w=dpa[w][now];
now--;
}
reverse(res.begin(),res.end());
for(int i=1;i<n;i++){
if(now>0&&vis[i]==0){
now--;
res.push_back(i);
}
}
for(auto x:res){
cout<<x<<" ";
}
cout<<endl;
}