답안 #13537 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13537	2015-02-23T11:02:18 Z	qja0950	K개의 묶음 (IZhO14_blocks)	C++	100 / 100	228 ms	46072 KB

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.0 / 14.0

#	결과	메모리	Grader output
1	Correct	45812 KB	Output is correct
2	Correct	45812 KB	Output is correct
3	Correct	45812 KB	Output is correct
4	Correct	45812 KB	Output is correct
5	Correct	45812 KB	Output is correct
6	Correct	45812 KB	Output is correct
7	Correct	45812 KB	Output is correct
8	Correct	45812 KB	Output is correct
9	Correct	45812 KB	Output is correct
10	Correct	45812 KB	Output is correct
11	Correct	45812 KB	Output is correct
12	Correct	45812 KB	Output is correct
13	Correct	45812 KB	Output is correct
14	Correct	45812 KB	Output is correct
15	Correct	45812 KB	Output is correct
16	Correct	45812 KB	Output is correct
17	Correct	45812 KB	Output is correct
18	Correct	45812 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	메모리	Grader output
1	Correct	45812 KB	Output is correct
2	Correct	45812 KB	Output is correct
3	Correct	45812 KB	Output is correct
4	Correct	45812 KB	Output is correct
5	Correct	45812 KB	Output is correct
6	Correct	45812 KB	Output is correct
7	Correct	45812 KB	Output is correct
8	Correct	45812 KB	Output is correct
9	Correct	45812 KB	Output is correct
10	Correct	45812 KB	Output is correct
11	Correct	45812 KB	Output is correct
12	Correct	45812 KB	Output is correct
13	Correct	45812 KB	Output is correct
14	Correct	45812 KB	Output is correct
15	Correct	45812 KB	Output is correct
16	Correct	45812 KB	Output is correct
17	Correct	45812 KB	Output is correct
18	Correct	45812 KB	Output is correct
19	Correct	45812 KB	Output is correct
20	Correct	45812 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	메모리	Grader output
1	Correct	45812 KB	Output is correct
2	Correct	45812 KB	Output is correct
3	Correct	45812 KB	Output is correct
4	Correct	45812 KB	Output is correct
5	Correct	45812 KB	Output is correct
6	Correct	45812 KB	Output is correct
7	Correct	45812 KB	Output is correct
8	Correct	45812 KB	Output is correct
9	Correct	45812 KB	Output is correct
10	Correct	45812 KB	Output is correct
11	Correct	45812 KB	Output is correct
12	Correct	45812 KB	Output is correct
13	Correct	45812 KB	Output is correct
14	Correct	45812 KB	Output is correct
15	Correct	45812 KB	Output is correct
16	Correct	45812 KB	Output is correct
17	Correct	45812 KB	Output is correct
18	Correct	45812 KB	Output is correct
19	Correct	45812 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	45812 KB	Output is correct
2	Correct	0 ms	45812 KB	Output is correct
3	Correct	6 ms	45812 KB	Output is correct
4	Correct	48 ms	45812 KB	Output is correct
5	Correct	137 ms	45812 KB	Output is correct
6	Correct	15 ms	45812 KB	Output is correct
7	Correct	67 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	Correct	0 ms	45812 KB	Output is correct
11	Correct	0 ms	45812 KB	Output is correct
12	Correct	0 ms	45812 KB	Output is correct
13	Correct	0 ms	45812 KB	Output is correct
14	Correct	14 ms	45812 KB	Output is correct
15	Correct	2 ms	45812 KB	Output is correct
16	Correct	6 ms	45812 KB	Output is correct
17	Correct	0 ms	45812 KB	Output is correct
18	Correct	12 ms	45812 KB	Output is correct
19	Correct	33 ms	45812 KB	Output is correct
20	Correct	104 ms	45812 KB	Output is correct
21	Correct	16 ms	45812 KB	Output is correct
22	Correct	61 ms	45812 KB	Output is correct
23	Correct	10 ms	45812 KB	Output is correct
24	Correct	25 ms	45812 KB	Output is correct
25	Correct	115 ms	45812 KB	Output is correct
26	Correct	0 ms	45812 KB	Output is correct
27	Correct	1 ms	45812 KB	Output is correct
28	Correct	19 ms	45812 KB	Output is correct
29	Correct	3 ms	45812 KB	Output is correct
30	Correct	9 ms	45812 KB	Output is correct
31	Correct	9 ms	45812 KB	Output is correct
32	Correct	15 ms	45940 KB	Output is correct
33	Correct	78 ms	45940 KB	Output is correct
34	Correct	228 ms	46072 KB	Output is correct
35	Correct	21 ms	46068 KB	Output is correct
36	Correct	108 ms	46068 KB	Output is correct
37	Correct	0 ms	45812 KB	Output is correct
38	Correct	9 ms	45812 KB	Output is correct
39	Correct	1 ms	45812 KB	Output is correct
40	Correct	0 ms	45812 KB	Output is correct
41	Correct	0 ms	45812 KB	Output is correct
42	Correct	0 ms	45812 KB	Output is correct

답안 #13537

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 21.0 / 21.0

Subtask #4 47.0 / 47.0

Subtask #1
14.0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
21.0 / 21.0

Subtask #4
47.0 / 47.0