답안 #54478 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54478	2018-07-03T15:12:00 Z	MladenP	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	410 ms	53900 KB

blocks

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%lld\n", x);
#define PRINT(x) fprintf(stderr, "%s = %lld\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
#define MAXK 110
stack<pii> s;
stack<int> mx;
int dp[MAXN][MAXK];
int a[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, K; cin >> N >> K;
    for(int i = 1; i <= N; i++) dp[i][0] = INF;
    for(int i = 1; i <= K; i++) {
        for(int j = 0; j < i; j++) dp[j][i] = INF;
    }
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int k = 1; k <= K; k++) {
        while(!s.empty()) s.pop();
        while(!mx.empty()) mx.pop();
        for(int n = 1; n <= N; n++) {
            int dpmin = dp[n-1][k-1];
            while(!s.empty() && a[n] >= s.top().fi) {
                dpmin = min(dpmin, s.top().se);
                s.pop();
                mx.pop();
            }

            s.push({a[n], dpmin});
            mx.push(min((!mx.empty() ? mx.top():INF), s.top().se+s.top().fi));
            dp[n][k] = mx.top();
            //PRINT(dp[n][k]);
        }
    }
    cout << dp[N][K];
    return 0;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	528 KB	Output is correct
4	Correct	3 ms	528 KB	Output is correct
5	Correct	2 ms	528 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	3 ms	716 KB	Output is correct
9	Correct	3 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	3 ms	772 KB	Output is correct
12	Correct	2 ms	772 KB	Output is correct
13	Correct	3 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	832 KB	Output is correct
17	Correct	2 ms	832 KB	Output is correct
18	Correct	2 ms	832 KB	Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	868 KB	Output is correct
2	Correct	2 ms	868 KB	Output is correct
3	Correct	2 ms	868 KB	Output is correct
4	Correct	2 ms	944 KB	Output is correct
5	Correct	2 ms	944 KB	Output is correct
6	Correct	2 ms	944 KB	Output is correct
7	Correct	2 ms	944 KB	Output is correct
8	Correct	2 ms	944 KB	Output is correct
9	Correct	2 ms	944 KB	Output is correct
10	Correct	2 ms	944 KB	Output is correct
11	Correct	2 ms	944 KB	Output is correct
12	Correct	3 ms	944 KB	Output is correct
13	Correct	3 ms	944 KB	Output is correct
14	Correct	3 ms	956 KB	Output is correct
15	Correct	2 ms	956 KB	Output is correct
16	Correct	2 ms	956 KB	Output is correct
17	Correct	3 ms	956 KB	Output is correct
18	Correct	2 ms	956 KB	Output is correct
19	Correct	2 ms	956 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	5280 KB	Output is correct
2	Correct	21 ms	20256 KB	Output is correct
3	Correct	26 ms	20256 KB	Output is correct
4	Correct	139 ms	20256 KB	Output is correct
5	Correct	410 ms	44440 KB	Output is correct
6	Correct	54 ms	44440 KB	Output is correct
7	Correct	242 ms	45088 KB	Output is correct
8	Correct	3 ms	45088 KB	Output is correct
9	Correct	2 ms	45088 KB	Output is correct
10	Correct	3 ms	45088 KB	Output is correct
11	Correct	2 ms	45088 KB	Output is correct
12	Correct	3 ms	45088 KB	Output is correct
13	Correct	4 ms	45088 KB	Output is correct
14	Correct	27 ms	45088 KB	Output is correct
15	Correct	7 ms	45088 KB	Output is correct
16	Correct	12 ms	45088 KB	Output is correct
17	Correct	21 ms	45088 KB	Output is correct
18	Correct	28 ms	45088 KB	Output is correct
19	Correct	138 ms	45088 KB	Output is correct
20	Correct	373 ms	47008 KB	Output is correct
21	Correct	54 ms	47524 KB	Output is correct
22	Correct	275 ms	48332 KB	Output is correct
23	Correct	53 ms	48876 KB	Output is correct
24	Correct	81 ms	49820 KB	Output is correct
25	Correct	379 ms	50356 KB	Output is correct
26	Correct	2 ms	50356 KB	Output is correct
27	Correct	2 ms	50356 KB	Output is correct
28	Correct	27 ms	50356 KB	Output is correct
29	Correct	7 ms	50356 KB	Output is correct
30	Correct	15 ms	50356 KB	Output is correct
31	Correct	22 ms	50356 KB	Output is correct
32	Correct	28 ms	50356 KB	Output is correct
33	Correct	106 ms	50356 KB	Output is correct
34	Correct	357 ms	52588 KB	Output is correct
35	Correct	64 ms	53268 KB	Output is correct
36	Correct	295 ms	53900 KB	Output is correct
37	Correct	9 ms	53900 KB	Output is correct
38	Correct	32 ms	53900 KB	Output is correct
39	Correct	2 ms	53900 KB	Output is correct
40	Correct	3 ms	53900 KB	Output is correct
41	Correct	2 ms	53900 KB	Output is correct
42	Correct	2 ms	53900 KB	Output is correct

답안 #54478

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