Submission #7135

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

blocks

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

using namespace std;

typedef pair <int,int> ppair;
typedef pair <ppair,int> pppair;
vector <pppair> 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<=K ; i++)
    {
        S.clear();
        for(j=i ; j<=N ; j++)
        {
            y=D[1-(i%2)][j-1];
            while(!S.empty() && S.back().first.first<=A[j])
            {
                if(y>S.back().first.second)
                    y=S.back().first.second;
                S.pop_back();
            }
            if(S.empty())
                x=INF;
            else
                x=S.back().second;
            if(x>A[j]+y)
                x=A[j]+y;
            S.push_back(make_pair(make_pair(A[j],y),x));
            D[i%2][j]=x;
        }
    }
}

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