Submission #7453

#	Time	Username	Problem	Language	Result	Execution time	Memory
7453		conankun	Split the sequence (APIO14_sequence)	C++98	0 / 100	0 ms	131072 KiB

sequence

#include <stdio.h>
int arr[1111111];
int dp[211][111111];
int bt[211][111111];
int sum[1111111];
int seq[111111];
int n,K;
int main()
{
    scanf("%d%d",&n,&K);
    int i,j,k;
    for(i=1;i<=n;i++) {
        scanf("%d",&sum[i]);
        sum[i] += sum[i-1];
    }
    dp[1][1]=sum[1] * (sum[n]-sum[1]);
    int ans=-1,kk=n;
    for(k=1;k<=K;k++){
        for(i=1;i<=n;i++){
            for(j=0;j<i;j++) {
                if(dp[k-1][j] + (sum[i]-sum[j])*(sum[n]-sum[i]) > dp[k][i]){
                    dp[k][i] = dp[k-1][j] + (sum[i]-sum[j])*(sum[n]-sum[i]);
                    bt[k][i] = j;
                    if(k==K && dp[k][i] >ans){
                        ans = dp[k][i];
                        kk=i;
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    int a=kk;
    seq[K+1]=kk;
    for(k=K;k>=1;k--){
        seq[k]=bt[k][a];
        a = bt[k][a];
    }
    for(i=2;i<=K+1;i++) printf("%d ",seq[i]);
}

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