Submission #7084

#	Time	Username	Problem	Language	Result	Execution time	Memory
7084		baneling100	Split the sequence (APIO14_sequence)	C++98	100 / 100	576 ms	82728 KiB

sequence

#include <stdio.h>

int N, K, Path[202][100002], S[100002], Top, Ans[202];
long long A[100002], D[2][100002];

void input(void)
{
    int i;

    scanf("%d %d",&N,&K);
    for(i=1 ; i<=N ; i++)
    {
        scanf("%lld",&A[i]);
        A[i]+=A[i-1];
    }
}

void process(void)
{
    int i, j, k, x, now;
    long long a, b, c, d, e, f;

    for(j=1 ; j<=K ; j++)
    {
        x=j%2;
        Top=0;
        now=1;
        for(k=j ; k<=N ; k++)
        {
            if(Top<2)
                S[++Top]=k;
            else
            {
                a=A[S[Top-1]];
                b=D[1-x][S[Top-1]]-A[S[Top-1]]*A[S[Top-1]];
                c=A[S[Top]];
                d=D[1-x][S[Top]]-A[S[Top]]*A[S[Top]];
                e=A[k];
                f=D[1-x][k]-A[k]*A[k];
                while(Top>=2 && (d-b)*(e-a)<=(c-a)*(f-b))
                {
                    Top--;
                    a=A[S[Top-1]];
                    b=D[1-x][S[Top-1]]-A[S[Top-1]]*A[S[Top-1]];
                    c=A[S[Top]];
                    d=D[1-x][S[Top]]-A[S[Top]]*A[S[Top]];
                }
                S[++Top]=k;
            }
            a=A[S[now]]*A[k+1]+D[1-x][S[now]]-A[S[now]]*A[S[now]];
            b=A[S[now+1]]*A[k+1]+D[1-x][S[now+1]]-A[S[now+1]]*A[S[now+1]];
            while(now<k && a<b)
            {
                now++;
                a=A[S[now]]*A[k+1]+D[1-x][S[now]]-A[S[now]]*A[S[now]];
                b=A[S[now+1]]*A[k+1]+D[1-x][S[now+1]]-A[S[now+1]]*A[S[now+1]];
            }
            D[x][k+1]=a;
            Path[j][k+1]=S[now];
        }
    }
    a=N;
    for(i=K ; i>=1 ; i--)
    {
        Ans[i]=Path[i][a];
        a=Path[i][a];
    }
}

void output(void)
{
    int i;

    printf("%lld\n",D[K%2][N]);
    for(i=1 ; i<=K ; i++)
        printf("%d ",Ans[i]);

}

int main(void)
{
    input();
    process();
    output();

    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