Submission #7151

#	Time	Username	Problem	Language	Result	Execution time	Memory
7151		baneling100	K blocks (IZhO14_blocks)	C++98	100 / 100	192 ms	3148 KiB

blocks

#include <stdio.h>
#include <vector>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
vector <ppair> S;
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, x, y;

    for(i=1 ; i<=N ; i++)
    {
        D[1][i]=D[1][i-1];
        if(D[1][i]<A[i])
            D[1][i]=A[i];
    }
    for(i=2 ; i<=K ; i++)
    {
        S.clear();
        for(j=i ; j<=N ; j++)
        {
            y=D[1-(i%2)][j-1];
            while(!S.empty() && S.back().first<=A[j])
            {
                if(y>S.back().second)
                    y=S.back().second;
                S.pop_back();
            }
            if(S.empty())
                x=INF;
            else
                x=S.back().first+S.back().second;
            if(x>A[j]+y)
            {
                x=A[j]+y;
                S.push_back(make_pair(A[j],y));
            }
            D[i%2][j]=x;
        }
    }
}

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

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

    return 0;
}

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