Submission #7914

#	Time	Username	Problem	Language	Result	Execution time	Memory
7914		woqja125	Split the sequence (APIO14_sequence)	C++98	100 / 100	1340 ms	86244 KiB

sequence

#include<stdio.h>
int dat[100001], sum[100001];
long long dp[2][100001];
long long Y[100001];
int p[210][100001];
void mkt(long long *T, long long *S, int *p, int f, int r, int s, int e)
{
    if(f>r) return;
    long long max = -1, t;
    int x = -1, i, m = (f+r)/2;
    for(i=s; i<=e && i<m; i++)
    {
        if(S[i] == -1) continue;
        t = S[i] + (1ll*sum[i]*(sum[m] - sum[i]));
        if(t>=max)
        {
            max = t;
            x = i;
        }
    }
    T[m] = max;
    p[m] = x;
    mkt(T, S, p, f, m-1, s, x);
    mkt(T, S, p, m+1, r, x, e);
}
int main()
{
    int n, k, i, j;
    scanf("%d%d", &n, &k); k++;
    for(i=1; i<=n; i++)
    {
        scanf("%d", &dat[i]);
        sum[i] = sum[i-1] + dat[i];
    }
    for(i=0; i<=1; i++)for(j=0; j<=n; j++) dp[i][j]=-1;
    for(j=0; j<=n; j++) dp[1][j] = 0;
    for(i=2; i<=k; i++)
    {
        for(j=0; j<=n; j++) dp[i%2][j] = -1;
        mkt(dp[i%2], dp[(i+1)%2], p[i], 0, n, 0, n);
    }
    printf("%lld\n", dp[k%2][n]);
    int x = n;
    for(int i=k; i>1; i--)
    {
        x = p[i][x];
        printf("%d ", x);
    }
    return 0;
}

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