Submission #13537

#	Time	Username	Problem	Language	Result	Execution time	Memory
13537		qja0950	K blocks (IZhO14_blocks)	C++98	100 / 100	228 ms	46072 KiB

blocks

//
//  main.cpp
//  IZhO14_blocks
//
//  Created by KJBS2 on 2015. 2. 23..
//  Copyright (c) 2015년 KJBS2. All rights reserved.
//

#include <stdio.h>
#include <stack>

#define MAX_N 101101
#define MAX_K 111

using namespace std;

int N, K;
int Nr[MAX_N];
int Dy[MAX_K][MAX_N];

stack< pair<int, int> > S;

int main() {
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++) {
        scanf("%d", &Nr[i]);
        Dy[1][i] = max(Nr[i], Dy[1][i-1]);
    }
    
    for(int k=1; k<K; k++) {
        
        while(!S.empty()) S.pop();
        
        for(int i=k+1; i<=N; i++) {
            int now = Nr[i];
            int block = Dy[k][i-1];
            
            while(!S.empty() && (S.top()).first <= now ) {
                if( (S.top()).second < block )
                    block = (S.top()).second;
                S.pop();
            }
            
            if(S.empty() || now + block <= ( (S.top()).first + (S.top()).second )  )
                S.push( make_pair(now, block) );

            Dy[k+1][i] = ( (S.top()).first + (S.top()).second );
//            printf("%d %d : <%d %d> %d\n", k+1, i, now, block, Dy[k+1][i]);
        }
    }
    
    printf("%d\n", Dy[K][N]);
    
    return 0;
}

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