Submission #50791

#	Time	Username	Problem	Language	Result	Execution time	Memory
50791		edisonhello	Split the sequence (APIO14_sequence)	C++11	0 / 100	2075 ms	85376 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,k;
ll a[100005],pre[100005],dp[105][100005];
int tp[105][100005];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i];
    memset(dp,0xb0,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=k;++i){
        tp[i][n+1]=n;
        for(int j=n;j>=i;--j){
            if(i==1)tp[i-1][j]=1;
            ll mx=LLONG_MIN;
            int p=-1;
            for(int k=tp[i-1][j];k<=tp[i][j+1];++k){
                ll val=(pre[n]-pre[j])*(pre[j]-pre[k-1])+dp[i-1][k-1];
                if(val>mx){
                    mx=val;
                    p=k;
                }
            }
            tp[i][j]=p;
            dp[i][j]=mx;
        }
    }
    ll mx=LLONG_MIN;
    int p=-1;
    for(int i=k;i<=n;++i){
        if(dp[k][i]>mx){
            mx=dp[k][i];
            p=i;
        }
    }
    cout<<mx<<endl;
    int zi=k,zj=p;
    stack<int> ans;
    while(zi){
        ans.push(tp[zi][zj]);
        zj=tp[zi][zj]-1;
        --zi;
    }
    while(ans.size()){
        cout<<ans.top()<<" ";
        ans.pop();
    }
    cout<<endl;
    /* for(int i=1;i<=k;++i){
        for(int j=1;j<=n;++j){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    } */
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29