Submission #5522

#	Time	Username	Problem	Language	Result	Execution time	Memory
5522		gs12117	Split the sequence (APIO14_sequence)	C++98	100 / 100	620 ms	86328 KiB

sequence

#include<stdio.h>
int n,m;
int a[100100];
long long int b[100100];
long long int dp[100100];
long long int ndp[100100];
int cutp[210][100100];
int deq[100100];
int cut[210];
int qs,qe;
int main(){
    int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i+1]=b[i]+a[i];
    }
    for(i=0;i<=n;i++){
        dp[i]=b[i]*b[i];
    }
    for(i=0;i<m;i++){
        ndp[0]=0;
        deq[0]=0;
        qs=0;
        qe=1;
        for(j=1;j<=n;j++){
            while(qs+1<qe&&dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]])>=dp[deq[qs+1]]+(b[j]-b[deq[qs+1]])*(b[j]-b[deq[qs+1]]))qs++;
            ndp[j]=dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]]);
            cutp[i+1][j]=deq[qs];
            while(qs+1<qe&&((long double)b[j]-b[deq[qe-1]])*(dp[deq[qe-1]]+b[deq[qe-1]]*b[deq[qe-1]]-dp[deq[qe-2]]-b[deq[qe-2]]*b[deq[qe-2]])>=((long double)b[deq[qe-1]]-b[deq[qe-2]])*(dp[j]+b[j]*b[j]-dp[deq[qe-1]]-b[deq[qe-1]]*b[deq[qe-1]]))qe--;
            deq[qe]=j;
            qe++;
        }
        for(j=0;j<=n;j++){
            dp[j]=ndp[j];
        }
    }
    printf("%lld\n",(b[n]*b[n]-dp[n])/2);
    j=n;
    for(i=m-1;i>=0;i--){
        j=cutp[i+1][j];
        cut[i]=j;
    }
    for(i=0;i<m;i++){
        printf("%d ",cut[i]);
    }
}

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