Submission #955843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
955843	2024-03-31T15:09:28 Z	gaoxam123	K blocks (IZhO14_blocks)	C++14	53 / 100	1000 ms	41820 KB

blocks

// https://oj.uz/problem/view/IZhO14_blocks
#include <bits/stdc++.h>
using namespace std;

int N, K;
int a[100005], dp[105][100005];

int main() {
    cin >> N >> K;
    memset(dp, 1000000, sizeof(dp));
    for(int i = 1; i <= N; i ++) {
        cin >> a[i];
    }
    // THIS VERSION IS NOT OPTIMIZED, BUT WORKS PROPERLY
    for(int i = 1; i <= K; i ++) {
        for(int j = i; j <= N; j ++) {
            if(i == 1) {
                if(j == 1) {
                    dp[i][j] = a[j];
                }
                else {
                    dp[i][j] = max(dp[i][j - 1], a[j]);
                }
            }
            else if(i == j) {
                dp[i][j] = dp[i - 1][j - 1] + a[j];
            }
            else {
                int mx = a[j];
                for(int k = j - 1; k >= i - 1; k --) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + mx);
                    mx = max(mx, a[k]);
                }
            }       
        }
    }
    cout << dp[K][N];
}

Subtask #1
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	41564 KB	Output is correct
2	Correct	6 ms	41564 KB	Output is correct
3	Correct	6 ms	41564 KB	Output is correct
4	Correct	6 ms	41564 KB	Output is correct
5	Correct	6 ms	41564 KB	Output is correct
6	Correct	6 ms	41564 KB	Output is correct
7	Correct	7 ms	41564 KB	Output is correct
8	Correct	6 ms	41564 KB	Output is correct
9	Correct	6 ms	41564 KB	Output is correct
10	Correct	6 ms	41648 KB	Output is correct
11	Correct	7 ms	41820 KB	Output is correct
12	Correct	6 ms	41564 KB	Output is correct
13	Correct	6 ms	41560 KB	Output is correct
14	Correct	6 ms	41564 KB	Output is correct
15	Correct	7 ms	41564 KB	Output is correct
16	Correct	6 ms	41564 KB	Output is correct
17	Correct	7 ms	41644 KB	Output is correct
18	Correct	6 ms	41560 KB	Output is correct

Subtask #2
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	41564 KB	Output is correct
2	Correct	6 ms	41564 KB	Output is correct
3	Correct	6 ms	41564 KB	Output is correct
4	Correct	6 ms	41564 KB	Output is correct
5	Correct	6 ms	41628 KB	Output is correct
6	Correct	7 ms	41564 KB	Output is correct
7	Correct	6 ms	41820 KB	Output is correct
8	Correct	6 ms	41560 KB	Output is correct
9	Correct	6 ms	41564 KB	Output is correct
10	Correct	6 ms	41600 KB	Output is correct
11	Correct	6 ms	41564 KB	Output is correct
12	Correct	6 ms	41564 KB	Output is correct
13	Correct	6 ms	41560 KB	Output is correct
14	Correct	6 ms	41564 KB	Output is correct
15	Correct	7 ms	41632 KB	Output is correct
16	Correct	6 ms	41560 KB	Output is correct
17	Correct	6 ms	41560 KB	Output is correct
18	Correct	7 ms	41564 KB	Output is correct
19	Correct	6 ms	41564 KB	Output is correct
20	Correct	6 ms	41560 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	41564 KB	Output is correct
2	Correct	6 ms	41564 KB	Output is correct
3	Correct	6 ms	41564 KB	Output is correct
4	Correct	6 ms	41564 KB	Output is correct
5	Correct	6 ms	41564 KB	Output is correct
6	Correct	6 ms	41564 KB	Output is correct
7	Correct	7 ms	41564 KB	Output is correct
8	Correct	6 ms	41564 KB	Output is correct
9	Correct	6 ms	41564 KB	Output is correct
10	Correct	6 ms	41648 KB	Output is correct
11	Correct	7 ms	41820 KB	Output is correct
12	Correct	6 ms	41564 KB	Output is correct
13	Correct	6 ms	41560 KB	Output is correct
14	Correct	6 ms	41564 KB	Output is correct
15	Correct	7 ms	41564 KB	Output is correct
16	Correct	6 ms	41564 KB	Output is correct
17	Correct	7 ms	41644 KB	Output is correct
18	Correct	6 ms	41560 KB	Output is correct
19	Correct	6 ms	41564 KB	Output is correct
20	Correct	6 ms	41564 KB	Output is correct
21	Correct	6 ms	41564 KB	Output is correct
22	Correct	6 ms	41564 KB	Output is correct
23	Correct	6 ms	41628 KB	Output is correct
24	Correct	7 ms	41564 KB	Output is correct
25	Correct	6 ms	41820 KB	Output is correct
26	Correct	6 ms	41560 KB	Output is correct
27	Correct	6 ms	41564 KB	Output is correct
28	Correct	6 ms	41600 KB	Output is correct
29	Correct	6 ms	41564 KB	Output is correct
30	Correct	6 ms	41564 KB	Output is correct
31	Correct	6 ms	41560 KB	Output is correct
32	Correct	6 ms	41564 KB	Output is correct
33	Correct	7 ms	41632 KB	Output is correct
34	Correct	6 ms	41560 KB	Output is correct
35	Correct	6 ms	41560 KB	Output is correct
36	Correct	7 ms	41564 KB	Output is correct
37	Correct	6 ms	41564 KB	Output is correct
38	Correct	6 ms	41560 KB	Output is correct
39	Correct	6 ms	41564 KB	Output is correct
40	Correct	6 ms	41632 KB	Output is correct
41	Correct	6 ms	41564 KB	Output is correct
42	Correct	7 ms	41620 KB	Output is correct
43	Correct	6 ms	41564 KB	Output is correct
44	Correct	6 ms	41612 KB	Output is correct
45	Correct	6 ms	41644 KB	Output is correct
46	Correct	6 ms	41760 KB	Output is correct
47	Correct	6 ms	41564 KB	Output is correct
48	Correct	7 ms	41564 KB	Output is correct
49	Correct	6 ms	41564 KB	Output is correct
50	Correct	6 ms	41596 KB	Output is correct
51	Correct	9 ms	41656 KB	Output is correct
52	Correct	6 ms	41564 KB	Output is correct
53	Correct	6 ms	41564 KB	Output is correct
54	Correct	6 ms	41560 KB	Output is correct
55	Correct	7 ms	41564 KB	Output is correct
56	Correct	6 ms	41564 KB	Output is correct
57	Correct	6 ms	41564 KB	Output is correct

Subtask #4
0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	41564 KB	Output is correct
2	Correct	6 ms	41564 KB	Output is correct
3	Correct	6 ms	41564 KB	Output is correct
4	Correct	6 ms	41564 KB	Output is correct
5	Correct	6 ms	41564 KB	Output is correct
6	Correct	6 ms	41564 KB	Output is correct
7	Correct	7 ms	41564 KB	Output is correct
8	Correct	6 ms	41564 KB	Output is correct
9	Correct	6 ms	41564 KB	Output is correct
10	Correct	6 ms	41648 KB	Output is correct
11	Correct	7 ms	41820 KB	Output is correct
12	Correct	6 ms	41564 KB	Output is correct
13	Correct	6 ms	41560 KB	Output is correct
14	Correct	6 ms	41564 KB	Output is correct
15	Correct	7 ms	41564 KB	Output is correct
16	Correct	6 ms	41564 KB	Output is correct
17	Correct	7 ms	41644 KB	Output is correct
18	Correct	6 ms	41560 KB	Output is correct
19	Correct	6 ms	41564 KB	Output is correct
20	Correct	6 ms	41564 KB	Output is correct
21	Correct	6 ms	41564 KB	Output is correct
22	Correct	6 ms	41564 KB	Output is correct
23	Correct	6 ms	41628 KB	Output is correct
24	Correct	7 ms	41564 KB	Output is correct
25	Correct	6 ms	41820 KB	Output is correct
26	Correct	6 ms	41560 KB	Output is correct
27	Correct	6 ms	41564 KB	Output is correct
28	Correct	6 ms	41600 KB	Output is correct
29	Correct	6 ms	41564 KB	Output is correct
30	Correct	6 ms	41564 KB	Output is correct
31	Correct	6 ms	41560 KB	Output is correct
32	Correct	6 ms	41564 KB	Output is correct
33	Correct	7 ms	41632 KB	Output is correct
34	Correct	6 ms	41560 KB	Output is correct
35	Correct	6 ms	41560 KB	Output is correct
36	Correct	7 ms	41564 KB	Output is correct
37	Correct	6 ms	41564 KB	Output is correct
38	Correct	6 ms	41560 KB	Output is correct
39	Correct	6 ms	41564 KB	Output is correct
40	Correct	6 ms	41632 KB	Output is correct
41	Correct	6 ms	41564 KB	Output is correct
42	Correct	7 ms	41620 KB	Output is correct
43	Correct	6 ms	41564 KB	Output is correct
44	Correct	6 ms	41612 KB	Output is correct
45	Correct	6 ms	41644 KB	Output is correct
46	Correct	6 ms	41760 KB	Output is correct
47	Correct	6 ms	41564 KB	Output is correct
48	Correct	7 ms	41564 KB	Output is correct
49	Correct	6 ms	41564 KB	Output is correct
50	Correct	6 ms	41596 KB	Output is correct
51	Correct	9 ms	41656 KB	Output is correct
52	Correct	6 ms	41564 KB	Output is correct
53	Correct	6 ms	41564 KB	Output is correct
54	Correct	6 ms	41560 KB	Output is correct
55	Correct	7 ms	41564 KB	Output is correct
56	Correct	6 ms	41564 KB	Output is correct
57	Correct	6 ms	41564 KB	Output is correct
58	Execution timed out	1058 ms	41564 KB	Time limit exceeded
59	Halted	0 ms	0 KB	-

Submission #955843

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 47.0

Subtask #1
14.0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 47.0