# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
161917 | HungAnhGoldIBO2020 | Split the sequence (APIO14_sequence) | C++14 | 1371 ms | 81588 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;
const int N=1e5+2;
const int K=201;
int n,pre[K][N];
long long dp[2][N],sum[N];
stack<int> lis;
void solve(int idx,int l,int r,int lef,int rig){
if(lef>rig){
return;
}
int i,mid=(lef+rig)>>1;
long long max1=-1;
for(i=min(mid-1,r);i>=l;i--){
if(max1<dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid])){
max1=dp[(idx+1)&1][i]+(sum[mid]-sum[i])*(sum[n]-sum[mid]);
pre[idx][mid]=i;
}
}
dp[idx&1][mid]=max1;
solve(idx,l,pre[idx][mid],lef,mid-1);
solve(idx,pre[idx][mid],r,mid+1,rig);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int i,j,k,l,num;
cin>>n>>num;
for(i=1;i<=n;i++){
cin>>j;
sum[i]=sum[i-1]+j;
}
for(i=1;i<=n;i++){
dp[1][i]=(sum[n]-sum[i])*sum[i];
pre[1][i]=i;
}
for(i=2;i<=num;i++){
solve(i,i-1,n-1,i,n-1);
}
j=n;
for(i=num;i<=n;i++){
if(dp[num&1][j]<dp[num&1][i]){
j=i;
}
}
cout<<dp[num&1][j]<<'\n';
for(i=num;i>0;i--){
lis.push(j);
j=pre[i][j];
}
while(lis.size()){
cout<<lis.top()<<' ';
lis.pop();
}
}
/*
7 3
4 1 3 4 0 2 3
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |