oj.uz

Submission #13534

# Submission time Handle Problem Language Result Execution time Memory
13534 2015-02-23T10:52:36 Z qja0950 K blocks (IZhO14_blocks) C++
0 / 100
 0 ms 45812 KB 
//
//  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++) {
        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\n", Dy[K][N]);
    
    return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45812 KB Output is correct
2 Correct 0 ms 45812 KB Output is correct
3 Correct 0 ms 45812 KB Output is correct
4 Correct 0 ms 45812 KB Output is correct
5 Correct 0 ms 45812 KB Output is correct
6 Correct 0 ms 45812 KB Output is correct
7 Correct 0 ms 45812 KB Output is correct
8 Correct 0 ms 45812 KB Output is correct
9 Correct 0 ms 45812 KB Output is correct
10 Incorrect 0 ms 45812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -