답안 #90669 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90669	2018-12-23T12:23:39 Z	P1QG	K개의 묶음 (IZhO14_blocks)	C++11	100 / 100	201 ms	42532 KB

blocks

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int K = 105;
const int INF = 0x3f3f3f3f;

int a[N];
int L[N], minF[N];
int dp[K][N];
int n, k;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]);
    for (int i = 2; i <= k; ++i) {
        stack<pair<int, int> > S;
        for (int j = i; j <= n; ++j) {
            int minF = dp[i - 1][j - 1];
            while (!S.empty() && a[S.top().second] <= a[j]) {
                minF = min(minF, S.top().first);
                S.pop();
            }
            dp[i][j] = min(dp[i][S.empty() ? 0 : S.top().second], minF + a[j]);
            S.push(make_pair(minF, j));
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	41464 KB	Output is correct
2	Correct	33 ms	41464 KB	Output is correct
3	Correct	34 ms	41496 KB	Output is correct
4	Correct	33 ms	41496 KB	Output is correct
5	Correct	34 ms	41544 KB	Output is correct
6	Correct	34 ms	41544 KB	Output is correct
7	Correct	34 ms	41544 KB	Output is correct
8	Correct	34 ms	41736 KB	Output is correct
9	Correct	35 ms	41736 KB	Output is correct
10	Correct	33 ms	41736 KB	Output is correct
11	Correct	34 ms	41736 KB	Output is correct
12	Correct	34 ms	41736 KB	Output is correct
13	Correct	34 ms	41736 KB	Output is correct
14	Correct	37 ms	41736 KB	Output is correct
15	Correct	35 ms	41736 KB	Output is correct
16	Correct	33 ms	41796 KB	Output is correct
17	Correct	34 ms	41796 KB	Output is correct
18	Correct	34 ms	41796 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	41796 KB	Output is correct
2	Correct	32 ms	41796 KB	Output is correct
3	Correct	33 ms	41836 KB	Output is correct
4	Correct	33 ms	41836 KB	Output is correct
5	Correct	35 ms	41836 KB	Output is correct
6	Correct	35 ms	41836 KB	Output is correct
7	Correct	35 ms	41836 KB	Output is correct
8	Correct	34 ms	41836 KB	Output is correct
9	Correct	30 ms	41836 KB	Output is correct
10	Correct	32 ms	41836 KB	Output is correct
11	Correct	33 ms	41836 KB	Output is correct
12	Correct	33 ms	41836 KB	Output is correct
13	Correct	34 ms	41836 KB	Output is correct
14	Correct	29 ms	41836 KB	Output is correct
15	Correct	33 ms	41836 KB	Output is correct
16	Correct	36 ms	41836 KB	Output is correct
17	Correct	29 ms	41836 KB	Output is correct
18	Correct	29 ms	41836 KB	Output is correct
19	Correct	34 ms	41836 KB	Output is correct
20	Correct	29 ms	41836 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	41836 KB	Output is correct
2	Correct	32 ms	41836 KB	Output is correct
3	Correct	29 ms	41836 KB	Output is correct
4	Correct	29 ms	41836 KB	Output is correct
5	Correct	29 ms	41836 KB	Output is correct
6	Correct	34 ms	41836 KB	Output is correct
7	Correct	35 ms	41836 KB	Output is correct
8	Correct	34 ms	41836 KB	Output is correct
9	Correct	29 ms	41836 KB	Output is correct
10	Correct	29 ms	41836 KB	Output is correct
11	Correct	30 ms	41836 KB	Output is correct
12	Correct	29 ms	41836 KB	Output is correct
13	Correct	29 ms	41836 KB	Output is correct
14	Correct	35 ms	41836 KB	Output is correct
15	Correct	31 ms	41836 KB	Output is correct
16	Correct	34 ms	41836 KB	Output is correct
17	Correct	34 ms	41836 KB	Output is correct
18	Correct	33 ms	41836 KB	Output is correct
19	Correct	35 ms	41836 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	41836 KB	Output is correct
2	Correct	43 ms	41872 KB	Output is correct
3	Correct	45 ms	41872 KB	Output is correct
4	Correct	78 ms	41872 KB	Output is correct
5	Correct	163 ms	42056 KB	Output is correct
6	Correct	62 ms	42168 KB	Output is correct
7	Correct	155 ms	42168 KB	Output is correct
8	Correct	29 ms	42168 KB	Output is correct
9	Correct	31 ms	42168 KB	Output is correct
10	Correct	30 ms	42168 KB	Output is correct
11	Correct	29 ms	42168 KB	Output is correct
12	Correct	34 ms	42168 KB	Output is correct
13	Correct	29 ms	42168 KB	Output is correct
14	Correct	45 ms	42168 KB	Output is correct
15	Correct	32 ms	42168 KB	Output is correct
16	Correct	35 ms	42168 KB	Output is correct
17	Correct	42 ms	42168 KB	Output is correct
18	Correct	47 ms	42168 KB	Output is correct
19	Correct	96 ms	42168 KB	Output is correct
20	Correct	201 ms	42168 KB	Output is correct
21	Correct	69 ms	42168 KB	Output is correct
22	Correct	126 ms	42168 KB	Output is correct
23	Correct	65 ms	42168 KB	Output is correct
24	Correct	81 ms	42168 KB	Output is correct
25	Correct	201 ms	42168 KB	Output is correct
26	Correct	34 ms	42168 KB	Output is correct
27	Correct	30 ms	42168 KB	Output is correct
28	Correct	49 ms	42168 KB	Output is correct
29	Correct	40 ms	42168 KB	Output is correct
30	Correct	37 ms	42168 KB	Output is correct
31	Correct	50 ms	42168 KB	Output is correct
32	Correct	47 ms	42168 KB	Output is correct
33	Correct	81 ms	42168 KB	Output is correct
34	Correct	184 ms	42532 KB	Output is correct
35	Correct	63 ms	42532 KB	Output is correct
36	Correct	123 ms	42532 KB	Output is correct
37	Correct	38 ms	42532 KB	Output is correct
38	Correct	47 ms	42532 KB	Output is correct
39	Correct	35 ms	42532 KB	Output is correct
40	Correct	35 ms	42532 KB	Output is correct
41	Correct	33 ms	42532 KB	Output is correct
42	Correct	33 ms	42532 KB	Output is correct

답안 #90669

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