답안 #90620 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90620	2018-12-23T01:04:40 Z	KenRoly	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	249 ms	54740 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	29 ms	41464 KB	Output is correct
2	Correct	29 ms	41464 KB	Output is correct
3	Correct	29 ms	41672 KB	Output is correct
4	Correct	29 ms	41672 KB	Output is correct
5	Correct	29 ms	41796 KB	Output is correct
6	Correct	29 ms	41796 KB	Output is correct
7	Correct	31 ms	41932 KB	Output is correct
8	Correct	30 ms	41972 KB	Output is correct
9	Correct	29 ms	41972 KB	Output is correct
10	Correct	31 ms	41972 KB	Output is correct
11	Correct	36 ms	41972 KB	Output is correct
12	Correct	30 ms	41996 KB	Output is correct
13	Correct	34 ms	41996 KB	Output is correct
14	Correct	34 ms	41996 KB	Output is correct
15	Correct	34 ms	41996 KB	Output is correct
16	Correct	32 ms	41996 KB	Output is correct
17	Correct	30 ms	41996 KB	Output is correct
18	Correct	29 ms	41996 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	41996 KB	Output is correct
2	Correct	29 ms	42028 KB	Output is correct
3	Correct	29 ms	42056 KB	Output is correct
4	Correct	29 ms	42068 KB	Output is correct
5	Correct	35 ms	42072 KB	Output is correct
6	Correct	29 ms	42076 KB	Output is correct
7	Correct	29 ms	42080 KB	Output is correct
8	Correct	29 ms	42084 KB	Output is correct
9	Correct	29 ms	42084 KB	Output is correct
10	Correct	34 ms	42216 KB	Output is correct
11	Correct	30 ms	42216 KB	Output is correct
12	Correct	34 ms	42216 KB	Output is correct
13	Correct	31 ms	42216 KB	Output is correct
14	Correct	31 ms	42216 KB	Output is correct
15	Correct	29 ms	42216 KB	Output is correct
16	Correct	29 ms	42216 KB	Output is correct
17	Correct	33 ms	42216 KB	Output is correct
18	Correct	29 ms	42216 KB	Output is correct
19	Correct	33 ms	42216 KB	Output is correct
20	Correct	35 ms	42216 KB	Output is correct

Subtask #3
21.0 / 21.0

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

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	42336 KB	Output is correct
2	Correct	49 ms	42764 KB	Output is correct
3	Correct	50 ms	43128 KB	Output is correct
4	Correct	82 ms	43464 KB	Output is correct
5	Correct	171 ms	44280 KB	Output is correct
6	Correct	72 ms	44996 KB	Output is correct
7	Correct	111 ms	45808 KB	Output is correct
8	Correct	33 ms	45808 KB	Output is correct
9	Correct	30 ms	45808 KB	Output is correct
10	Correct	34 ms	45808 KB	Output is correct
11	Correct	29 ms	45808 KB	Output is correct
12	Correct	30 ms	45808 KB	Output is correct
13	Correct	29 ms	45808 KB	Output is correct
14	Correct	52 ms	45808 KB	Output is correct
15	Correct	32 ms	45808 KB	Output is correct
16	Correct	35 ms	45808 KB	Output is correct
17	Correct	43 ms	45996 KB	Output is correct
18	Correct	46 ms	46320 KB	Output is correct
19	Correct	87 ms	46596 KB	Output is correct
20	Correct	249 ms	47540 KB	Output is correct
21	Correct	62 ms	48212 KB	Output is correct
22	Correct	123 ms	48888 KB	Output is correct
23	Correct	86 ms	49656 KB	Output is correct
24	Correct	73 ms	50248 KB	Output is correct
25	Correct	198 ms	50948 KB	Output is correct
26	Correct	29 ms	50948 KB	Output is correct
27	Correct	36 ms	50948 KB	Output is correct
28	Correct	49 ms	50948 KB	Output is correct
29	Correct	38 ms	50948 KB	Output is correct
30	Correct	40 ms	50988 KB	Output is correct
31	Correct	48 ms	51240 KB	Output is correct
32	Correct	53 ms	51672 KB	Output is correct
33	Correct	87 ms	52076 KB	Output is correct
34	Correct	200 ms	53244 KB	Output is correct
35	Correct	72 ms	53776 KB	Output is correct
36	Correct	122 ms	54740 KB	Output is correct
37	Correct	37 ms	54740 KB	Output is correct
38	Correct	47 ms	54740 KB	Output is correct
39	Correct	35 ms	54740 KB	Output is correct
40	Correct	35 ms	54740 KB	Output is correct
41	Correct	34 ms	54740 KB	Output is correct
42	Correct	34 ms	54740 KB	Output is correct

답안 #90620

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