답안 #791842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791842	2023-07-24T10:54:08 Z	이성호(#10048)	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	433 ms	70888 KB

Main

#include <iostream>
#include <string>
#include <algorithm>
#define int long long
using namespace std;
const int inf = 1e18;

int N, V[2048][2048];
int dp[2048][2048];
pair<int, int> lca(int i, int j)
{
    int cc = 0;
    while (i != j) {
        i >>= 1; j >>= 1; cc++;
    }
    return make_pair(i, cc);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> V[i][j];
        }
    }
    int cnt = 0;
    while ((1 << cnt) != N) cnt++;
    fill(&dp[0][0], &dp[2047][2048], inf);
    for (int j = 0; j < N; j++) dp[0][j] = 0;
    for (int i = 1; i < N; i++) {
        pair<int, int> bef = lca(i-1, i);
        for (int j = 0; j < N; j++) {
            int p = (j >> bef.second - 1) << (bef.second - 1);
            p ^= 1 << bef.second - 1;
            int q = p + (1 << bef.second - 1) - 1;
            for (int k = p; k <= q; k++) {
                dp[i][j] = min(dp[i][j], dp[i-1][k] + V[k][j]);
            }
        }
    }
    int ans = inf;
    for (int i = 0; i < N; i++) ans = min(ans, dp[N-1][i]);
    cout << ans << '\n';
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:34:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   34 |             int p = (j >> bef.second - 1) << (bef.second - 1);
      |                           ~~~~~~~~~~~^~~
Main.cpp:35:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |             p ^= 1 << bef.second - 1;
      |                       ~~~~~~~~~~~^~~
Main.cpp:36:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |             int q = p + (1 << bef.second - 1) - 1;
      |                               ~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	33108 KB	Output is correct
2	Correct	15 ms	33208 KB	Output is correct
3	Correct	14 ms	33160 KB	Output is correct
4	Correct	14 ms	33108 KB	Output is correct
5	Correct	14 ms	33208 KB	Output is correct
6	Correct	14 ms	33140 KB	Output is correct
7	Correct	14 ms	33200 KB	Output is correct
8	Correct	14 ms	33164 KB	Output is correct
9	Correct	14 ms	33108 KB	Output is correct
10	Correct	14 ms	33172 KB	Output is correct
11	Correct	14 ms	33108 KB	Output is correct
12	Correct	13 ms	33196 KB	Output is correct
13	Correct	14 ms	33132 KB	Output is correct
14	Correct	14 ms	33200 KB	Output is correct
15	Correct	14 ms	33108 KB	Output is correct
16	Correct	14 ms	33108 KB	Output is correct
17	Correct	16 ms	33216 KB	Output is correct
18	Correct	13 ms	33108 KB	Output is correct
19	Correct	13 ms	33108 KB	Output is correct
20	Correct	13 ms	33120 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	33108 KB	Output is correct
2	Correct	15 ms	33208 KB	Output is correct
3	Correct	14 ms	33160 KB	Output is correct
4	Correct	14 ms	33108 KB	Output is correct
5	Correct	14 ms	33208 KB	Output is correct
6	Correct	14 ms	33140 KB	Output is correct
7	Correct	14 ms	33200 KB	Output is correct
8	Correct	14 ms	33164 KB	Output is correct
9	Correct	14 ms	33108 KB	Output is correct
10	Correct	14 ms	33172 KB	Output is correct
11	Correct	14 ms	33108 KB	Output is correct
12	Correct	13 ms	33196 KB	Output is correct
13	Correct	14 ms	33132 KB	Output is correct
14	Correct	14 ms	33200 KB	Output is correct
15	Correct	14 ms	33108 KB	Output is correct
16	Correct	14 ms	33108 KB	Output is correct
17	Correct	16 ms	33216 KB	Output is correct
18	Correct	13 ms	33108 KB	Output is correct
19	Correct	13 ms	33108 KB	Output is correct
20	Correct	13 ms	33120 KB	Output is correct
21	Correct	15 ms	33620 KB	Output is correct
22	Correct	15 ms	33620 KB	Output is correct
23	Correct	15 ms	33620 KB	Output is correct
24	Correct	14 ms	33364 KB	Output is correct
25	Correct	14 ms	33376 KB	Output is correct
26	Correct	16 ms	33568 KB	Output is correct
27	Correct	15 ms	33664 KB	Output is correct
28	Correct	15 ms	33704 KB	Output is correct
29	Correct	16 ms	33676 KB	Output is correct
30	Correct	15 ms	33628 KB	Output is correct
31	Correct	16 ms	33588 KB	Output is correct
32	Correct	16 ms	33616 KB	Output is correct
33	Correct	16 ms	33620 KB	Output is correct
34	Correct	19 ms	33664 KB	Output is correct
35	Correct	16 ms	33560 KB	Output is correct
36	Correct	15 ms	33620 KB	Output is correct
37	Correct	15 ms	33644 KB	Output is correct
38	Correct	15 ms	33608 KB	Output is correct
39	Correct	14 ms	33668 KB	Output is correct
40	Correct	15 ms	33620 KB	Output is correct

Subtask #3
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	33108 KB	Output is correct
2	Correct	15 ms	33208 KB	Output is correct
3	Correct	14 ms	33160 KB	Output is correct
4	Correct	14 ms	33108 KB	Output is correct
5	Correct	14 ms	33208 KB	Output is correct
6	Correct	14 ms	33140 KB	Output is correct
7	Correct	14 ms	33200 KB	Output is correct
8	Correct	14 ms	33164 KB	Output is correct
9	Correct	14 ms	33108 KB	Output is correct
10	Correct	14 ms	33172 KB	Output is correct
11	Correct	14 ms	33108 KB	Output is correct
12	Correct	13 ms	33196 KB	Output is correct
13	Correct	14 ms	33132 KB	Output is correct
14	Correct	14 ms	33200 KB	Output is correct
15	Correct	14 ms	33108 KB	Output is correct
16	Correct	14 ms	33108 KB	Output is correct
17	Correct	16 ms	33216 KB	Output is correct
18	Correct	13 ms	33108 KB	Output is correct
19	Correct	13 ms	33108 KB	Output is correct
20	Correct	13 ms	33120 KB	Output is correct
21	Correct	15 ms	33620 KB	Output is correct
22	Correct	15 ms	33620 KB	Output is correct
23	Correct	15 ms	33620 KB	Output is correct
24	Correct	14 ms	33364 KB	Output is correct
25	Correct	14 ms	33376 KB	Output is correct
26	Correct	16 ms	33568 KB	Output is correct
27	Correct	15 ms	33664 KB	Output is correct
28	Correct	15 ms	33704 KB	Output is correct
29	Correct	16 ms	33676 KB	Output is correct
30	Correct	15 ms	33628 KB	Output is correct
31	Correct	16 ms	33588 KB	Output is correct
32	Correct	16 ms	33616 KB	Output is correct
33	Correct	16 ms	33620 KB	Output is correct
34	Correct	19 ms	33664 KB	Output is correct
35	Correct	16 ms	33560 KB	Output is correct
36	Correct	15 ms	33620 KB	Output is correct
37	Correct	15 ms	33644 KB	Output is correct
38	Correct	15 ms	33608 KB	Output is correct
39	Correct	14 ms	33668 KB	Output is correct
40	Correct	15 ms	33620 KB	Output is correct
41	Correct	38 ms	37204 KB	Output is correct
42	Correct	44 ms	37376 KB	Output is correct
43	Correct	38 ms	37224 KB	Output is correct
44	Correct	39 ms	37164 KB	Output is correct
45	Correct	39 ms	37216 KB	Output is correct
46	Correct	39 ms	37192 KB	Output is correct
47	Correct	38 ms	37220 KB	Output is correct
48	Correct	39 ms	37128 KB	Output is correct
49	Correct	39 ms	37196 KB	Output is correct
50	Correct	39 ms	37264 KB	Output is correct
51	Correct	39 ms	37212 KB	Output is correct
52	Correct	37 ms	37176 KB	Output is correct
53	Correct	37 ms	37196 KB	Output is correct
54	Correct	38 ms	37236 KB	Output is correct
55	Correct	39 ms	37232 KB	Output is correct
56	Correct	39 ms	38768 KB	Output is correct
57	Correct	39 ms	39040 KB	Output is correct
58	Correct	39 ms	38976 KB	Output is correct
59	Correct	39 ms	38988 KB	Output is correct
60	Correct	38 ms	38636 KB	Output is correct

Subtask #4
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	33108 KB	Output is correct
2	Correct	15 ms	33208 KB	Output is correct
3	Correct	14 ms	33160 KB	Output is correct
4	Correct	14 ms	33108 KB	Output is correct
5	Correct	14 ms	33208 KB	Output is correct
6	Correct	14 ms	33140 KB	Output is correct
7	Correct	14 ms	33200 KB	Output is correct
8	Correct	14 ms	33164 KB	Output is correct
9	Correct	14 ms	33108 KB	Output is correct
10	Correct	14 ms	33172 KB	Output is correct
11	Correct	14 ms	33108 KB	Output is correct
12	Correct	13 ms	33196 KB	Output is correct
13	Correct	14 ms	33132 KB	Output is correct
14	Correct	14 ms	33200 KB	Output is correct
15	Correct	14 ms	33108 KB	Output is correct
16	Correct	14 ms	33108 KB	Output is correct
17	Correct	16 ms	33216 KB	Output is correct
18	Correct	13 ms	33108 KB	Output is correct
19	Correct	13 ms	33108 KB	Output is correct
20	Correct	13 ms	33120 KB	Output is correct
21	Correct	15 ms	33620 KB	Output is correct
22	Correct	15 ms	33620 KB	Output is correct
23	Correct	15 ms	33620 KB	Output is correct
24	Correct	14 ms	33364 KB	Output is correct
25	Correct	14 ms	33376 KB	Output is correct
26	Correct	16 ms	33568 KB	Output is correct
27	Correct	15 ms	33664 KB	Output is correct
28	Correct	15 ms	33704 KB	Output is correct
29	Correct	16 ms	33676 KB	Output is correct
30	Correct	15 ms	33628 KB	Output is correct
31	Correct	16 ms	33588 KB	Output is correct
32	Correct	16 ms	33616 KB	Output is correct
33	Correct	16 ms	33620 KB	Output is correct
34	Correct	19 ms	33664 KB	Output is correct
35	Correct	16 ms	33560 KB	Output is correct
36	Correct	15 ms	33620 KB	Output is correct
37	Correct	15 ms	33644 KB	Output is correct
38	Correct	15 ms	33608 KB	Output is correct
39	Correct	14 ms	33668 KB	Output is correct
40	Correct	15 ms	33620 KB	Output is correct
41	Correct	38 ms	37204 KB	Output is correct
42	Correct	44 ms	37376 KB	Output is correct
43	Correct	38 ms	37224 KB	Output is correct
44	Correct	39 ms	37164 KB	Output is correct
45	Correct	39 ms	37216 KB	Output is correct
46	Correct	39 ms	37192 KB	Output is correct
47	Correct	38 ms	37220 KB	Output is correct
48	Correct	39 ms	37128 KB	Output is correct
49	Correct	39 ms	37196 KB	Output is correct
50	Correct	39 ms	37264 KB	Output is correct
51	Correct	39 ms	37212 KB	Output is correct
52	Correct	37 ms	37176 KB	Output is correct
53	Correct	37 ms	37196 KB	Output is correct
54	Correct	38 ms	37236 KB	Output is correct
55	Correct	39 ms	37232 KB	Output is correct
56	Correct	39 ms	38768 KB	Output is correct
57	Correct	39 ms	39040 KB	Output is correct
58	Correct	39 ms	38976 KB	Output is correct
59	Correct	39 ms	38988 KB	Output is correct
60	Correct	38 ms	38636 KB	Output is correct
61	Correct	421 ms	69752 KB	Output is correct
62	Correct	433 ms	67944 KB	Output is correct
63	Correct	431 ms	70832 KB	Output is correct
64	Correct	422 ms	67912 KB	Output is correct
65	Correct	430 ms	69160 KB	Output is correct
66	Correct	427 ms	69960 KB	Output is correct
67	Correct	422 ms	68428 KB	Output is correct
68	Correct	428 ms	70888 KB	Output is correct
69	Correct	431 ms	65952 KB	Output is correct
70	Correct	418 ms	67428 KB	Output is correct
71	Correct	431 ms	68364 KB	Output is correct
72	Correct	419 ms	69172 KB	Output is correct
73	Correct	433 ms	68972 KB	Output is correct
74	Correct	432 ms	68984 KB	Output is correct
75	Correct	426 ms	69000 KB	Output is correct
76	Correct	430 ms	69076 KB	Output is correct
77	Correct	418 ms	68696 KB	Output is correct
78	Correct	432 ms	68780 KB	Output is correct
79	Correct	422 ms	68828 KB	Output is correct
80	Correct	420 ms	68660 KB	Output is correct

답안 #791842

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 17.0 / 17.0

Subtask #3 32.0 / 32.0

Subtask #4 41.0 / 41.0

Subtask #1
10.0 / 10.0

Subtask #2
17.0 / 17.0

Subtask #3
32.0 / 32.0

Subtask #4
41.0 / 41.0