Submission #7129

#	Time	Username	Problem	Language	Result	Execution time	Memory
7129		baneling100	K blocks (IZhO14_blocks)	C++98	0 / 100	4 ms	2260 KiB

blocks

#include <stdio.h>

int N, K, A[100001], D[2][100001];

void input(void)
{
    int i;

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

void process(void)
{
    int i, j, Max;

    for(i=1 ; i<=K ; i++)
    {
        Max=A[i];
        D[i%2][i]=D[1-(i%2)][i-1]+A[i];
        for(j=i+1 ; j<=N ; j++)
        {
            if(Max<A[j])
            {
                D[i%2][j]=D[i%2][j-1]+A[j]-Max;
                Max=A[j];
            }
            else
                D[i%2][j]=D[i%2][j-1];
            if(D[i%2][j]>D[1-(i%2)][j-1]+A[j])
                D[i%2][j]=D[1-(i%2)][j-1]+A[j];
        }
    }
}

void output(void)
{
    printf("%d",D[K%2][N]);
}

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

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47