CSES - Aalto Competitive Programming 2024 - wk5 - Mon - Results
Submission details
Task:Kindergarten
Sender:aalto2024e_003
Submission time:2024-09-30 17:10:24 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.05 sdetails
#32ACCEPTED0.05 sdetails
#33ACCEPTED0.05 sdetails
#34ACCEPTED0.05 sdetails
#35ACCEPTED0.05 sdetails
#36ACCEPTED0.05 sdetails
#37ACCEPTED0.05 sdetails
#38ACCEPTED0.05 sdetails
#39ACCEPTED0.05 sdetails
#40ACCEPTED0.05 sdetails
#41ACCEPTED0.05 sdetails
#42ACCEPTED0.05 sdetails
#43ACCEPTED0.05 sdetails
#44ACCEPTED0.05 sdetails
#45ACCEPTED0.05 sdetails
#46ACCEPTED0.05 sdetails
#47ACCEPTED0.05 sdetails
#48ACCEPTED0.05 sdetails
#49ACCEPTED0.05 sdetails
#50ACCEPTED0.04 sdetails
#51ACCEPTED0.05 sdetails
#52ACCEPTED0.05 sdetails
#53ACCEPTED0.05 sdetails
#54ACCEPTED0.05 sdetails
#55ACCEPTED0.05 sdetails
#56ACCEPTED0.05 sdetails
#57ACCEPTED0.05 sdetails
#58ACCEPTED0.05 sdetails
#59ACCEPTED0.05 sdetails
#60ACCEPTED0.05 sdetails
#61ACCEPTED0.05 sdetails
#62ACCEPTED0.05 sdetails
#63ACCEPTED0.05 sdetails
#64ACCEPTED0.05 sdetails
#65ACCEPTED0.05 sdetails
#66ACCEPTED0.05 sdetails
#67ACCEPTED0.05 sdetails
#68ACCEPTED0.05 sdetails
#69ACCEPTED0.05 sdetails
#70ACCEPTED0.05 sdetails
#71ACCEPTED0.05 sdetails
#72ACCEPTED0.05 sdetails
#73ACCEPTED0.05 sdetails
#74ACCEPTED0.05 sdetails
#75ACCEPTED0.05 sdetails
#76ACCEPTED0.05 sdetails
#77ACCEPTED0.05 sdetails
#78ACCEPTED0.05 sdetails
#79ACCEPTED0.05 sdetails
#80ACCEPTED0.05 sdetails
#81ACCEPTED0.05 sdetails
#82ACCEPTED0.05 sdetails
#83ACCEPTED0.05 sdetails
#84ACCEPTED0.05 sdetails
#85ACCEPTED0.05 sdetails
#86ACCEPTED0.05 sdetails
#87ACCEPTED0.05 sdetails
#88ACCEPTED0.05 sdetails
#89ACCEPTED0.05 sdetails
#90ACCEPTED0.05 sdetails

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> rivalry_matrix(n, vector<int>(n));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> rivalry_matrix[i][j];
        }
    }

    int full_mask = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));

    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 0;
    }

    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (mask & (1 << u)) {
                for (int v = 0; v < n; ++v) {
                    if (!(mask & (1 << v))) {
                        int new_mask = mask | (1 << v);
                        dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + rivalry_matrix[u][v]);
                    }
                }
            }
        }
    }

    int result = INT_MAX;
    for (int i = 0; i < n; ++i) {
        result = min(result, dp[full_mask][i]);
    }

    cout << result << endl;

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
0

user output
0

Test 2

Verdict: ACCEPTED

input
1

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
2
4 0 
0 10 

correct output
0

user output
0

Test 4

Verdict: ACCEPTED

input
2
6 7 
7 9 

correct output
7

user output
7

Test 5

Verdict: ACCEPTED

input
3
10 1 7 
1 10 6 
7 6 7 

correct output
7

user output
7

Test 6

Verdict: ACCEPTED

input
3
2 9 10 
9 2 10 
10 10 5 

correct output
19

user output
19

Test 7

Verdict: ACCEPTED

input
3
9 2 0 
2 9 4 
0 4 1 

correct output
2

user output
2

Test 8

Verdict: ACCEPTED

input
4
0 4 10 5 
4 10 3 0 
10 3 5 0 
5 0 0 4 

correct output
4

user output
4

Test 9

Verdict: ACCEPTED

input
4
9 9 2 4 
9 4 4 8 
2 4 0 4 
4 8 4 4 

correct output
10

user output
10

Test 10

Verdict: ACCEPTED

input
4
0 5 1 4 
5 0 0 1 
1 0 2 2 
4 1 2 1 

correct output
2

user output
2

Test 11

Verdict: ACCEPTED

input
5
7 4 3 7 1 
4 1 6 6 1 
3 6 10 0 5 
7 6 0 4 2 
...

correct output
5

user output
5

Test 12

Verdict: ACCEPTED

input
5
3 6 1 10 0 
6 10 2 0 9 
1 2 9 9 4 
10 0 9 5 6 
...

correct output
3

user output
3

Test 13

Verdict: ACCEPTED

input
5
9 3 8 3 1 
3 10 3 6 0 
8 3 1 8 3 
3 6 8 6 3 
...

correct output
7

user output
7

Test 14

Verdict: ACCEPTED

input
5
2 10 2 9 10 
10 2 6 7 2 
2 6 0 0 4 
9 7 0 5 10 
...

correct output
11

user output
11

Test 15

Verdict: ACCEPTED

input
5
0 4 10 4 0 
4 6 8 2 8 
10 8 4 8 7 
4 2 8 4 9 
...

correct output
13

user output
13

Test 16

Verdict: ACCEPTED

input
5
5 2 1 3 8 
2 3 5 7 8 
1 5 6 9 0 
3 7 9 7 2 
...

correct output
5

user output
5

Test 17

Verdict: ACCEPTED

input
5
8 9 3 4 10 
9 1 10 6 8 
3 10 2 8 9 
4 6 8 0 0 
...

correct output
15

user output
15

Test 18

Verdict: ACCEPTED

input
5
10 8 7 6 8 
8 6 0 3 6 
7 0 1 1 6 
6 3 1 8 6 
...

correct output
13

user output
13

Test 19

Verdict: ACCEPTED

input
5
4 9 6 1 3 
9 7 5 2 8 
6 5 2 9 4 
1 2 9 0 7 
...

correct output
10

user output
10

Test 20

Verdict: ACCEPTED

input
5
6 4 5 7 8 
4 1 4 6 5 
5 4 5 2 10 
7 6 2 10 2 
...

correct output
12

user output
12

Test 21

Verdict: ACCEPTED

input
10
549 646 792 87 979 640 264 618...

correct output
1257

user output
1257

Test 22

Verdict: ACCEPTED

input
10
417 92 419 671 801 895 98 315 ...

correct output
1093

user output
1093

Test 23

Verdict: ACCEPTED

input
10
436 330 621 786 505 597 468 38...

correct output
1912

user output
1912

Test 24

Verdict: ACCEPTED

input
10
551 897 29 591 283 781 976 92 ...

correct output
1530

user output
1530

Test 25

Verdict: ACCEPTED

input
10
967 216 780 597 436 75 528 545...

correct output
1166

user output
1166

Test 26

Verdict: ACCEPTED

input
10
222 612 80 274 600 144 24 578 ...

correct output
1310

user output
1310

Test 27

Verdict: ACCEPTED

input
10
893 595 438 991 54 541 717 718...

correct output
1942

user output
1942

Test 28

Verdict: ACCEPTED

input
10
76 539 679 910 601 133 205 838...

correct output
2202

user output
2202

Test 29

Verdict: ACCEPTED

input
10
874 11 555 426 65 224 28 320 6...

correct output
987

user output
987

Test 30

Verdict: ACCEPTED

input
10
10 218 166 573 386 804 650 874...

correct output
1545

user output
1545

Test 31

Verdict: ACCEPTED

input
16
78876117 17293464 73807511 451...

correct output
141535044

user output
141535044

Test 32

Verdict: ACCEPTED

input
16
18434581 96310208 2094677 8835...

correct output
217719706

user output
217719706

Test 33

Verdict: ACCEPTED

input
16
15764865 97858716 92778181 718...

correct output
167604914

user output
167604914

Test 34

Verdict: ACCEPTED

input
16
79528724 65612103 26207475 638...

correct output
140515513

user output
140515513

Test 35

Verdict: ACCEPTED

input
16
52556424 55139192 95364389 546...

correct output
140013397

user output
140013397

Test 36

Verdict: ACCEPTED

input
16
86801053 11426789 72187831 966...

correct output
93732738

user output
93732738

Test 37

Verdict: ACCEPTED

input
16
22833997 7191499 71236196 3216...

correct output
115026040

user output
115026040

Test 38

Verdict: ACCEPTED

input
16
30132775 3994617 56422716 4279...

correct output
122521730

user output
122521730

Test 39

Verdict: ACCEPTED

input
16
66508002 86884113 88110850 970...

correct output
206680250

user output
206680250

Test 40

Verdict: ACCEPTED

input
16
9973896 65003382 54473078 6575...

correct output
105290977

user output
105290977

Test 41

Verdict: ACCEPTED

input
16
60142917 67282857 11933232 463...

correct output
149892373

user output
149892373

Test 42

Verdict: ACCEPTED

input
16
4982660 31508124 77610451 9338...

correct output
208191625

user output
208191625

Test 43

Verdict: ACCEPTED

input
16
21317409 22538814 78950075 437...

correct output
141684927

user output
141684927

Test 44

Verdict: ACCEPTED

input
16
52899464 63202728 6654687 1447...

correct output
162046504

user output
162046504

Test 45

Verdict: ACCEPTED

input
16
98172450 57262621 54713540 967...

correct output
151356452

user output
151356452

Test 46

Verdict: ACCEPTED

input
16
88979873 56880637 33342355 868...

correct output
159671124

user output
159671124

Test 47

Verdict: ACCEPTED

input
16
31489774 75583422 98416671 495...

correct output
177673400

user output
177673400

Test 48

Verdict: ACCEPTED

input
16
43534750 41244279 21038793 242...

correct output
174069522

user output
174069522

Test 49

Verdict: ACCEPTED

input
16
74549766 97697405 65731362 223...

correct output
164091596

user output
164091596

Test 50

Verdict: ACCEPTED

input
16
88329068 78556994 29213132 737...

correct output
150948961

user output
150948961

Test 51

Verdict: ACCEPTED

input
16
11868309 52454190 2188140 3426...

correct output
145704982

user output
145704982

Test 52

Verdict: ACCEPTED

input
16
62601211 24407904 38967625 742...

correct output
165774974

user output
165774974

Test 53

Verdict: ACCEPTED

input
16
38353763 90537037 98227382 885...

correct output
128735723

user output
128735723

Test 54

Verdict: ACCEPTED

input
16
87124995 71164598 85140576 178...

correct output
88146905

user output
88146905

Test 55

Verdict: ACCEPTED

input
16
15506055 73736552 44372116 853...

correct output
139764802

user output
139764802

Test 56

Verdict: ACCEPTED

input
16
20052620 55628826 15868440 899...

correct output
112678656

user output
112678656

Test 57

Verdict: ACCEPTED

input
16
38365166 78120078 30444983 287...

correct output
180080436

user output
180080436

Test 58

Verdict: ACCEPTED

input
16
46161809 99247781 74790752 906...

correct output
192231810

user output
192231810

Test 59

Verdict: ACCEPTED

input
16
96396611 61707575 39771927 957...

correct output
157075200

user output
157075200

Test 60

Verdict: ACCEPTED

input
16
86701456 19718778 48320555 202...

correct output
171350081

user output
171350081

Test 61

Verdict: ACCEPTED

input
16
10218362 40742172 91128924 285...

correct output
127429234

user output
127429234

Test 62

Verdict: ACCEPTED

input
16
79903579 1974104 24354885 4902...

correct output
119531862

user output
119531862

Test 63

Verdict: ACCEPTED

input
16
23816783 24638719 49178170 814...

correct output
161233528

user output
161233528

Test 64

Verdict: ACCEPTED

input
16
22336543 34284046 7826114 4407...

correct output
172344121

user output
172344121

Test 65

Verdict: ACCEPTED

input
16
4933488 53040995 75121239 3334...

correct output
150345908

user output
150345908

Test 66

Verdict: ACCEPTED

input
16
15740195 82161403 83343605 558...

correct output
177299100

user output
177299100

Test 67

Verdict: ACCEPTED

input
16
3639374 43311419 10627086 4629...

correct output
181883199

user output
181883199

Test 68

Verdict: ACCEPTED

input
16
10600561 29567300 26714920 537...

correct output
153201253

user output
153201253

Test 69

Verdict: ACCEPTED

input
16
34181158 4262559 25064528 1281...

correct output
110754397

user output
110754397

Test 70

Verdict: ACCEPTED

input
16
1379850 55703817 5455026 69880...

correct output
150243591

user output
150243591

Test 71

Verdict: ACCEPTED

input
16
69328497 20779089 35701876 660...

correct output
163180293

user output
163180293

Test 72

Verdict: ACCEPTED

input
16
11384815 61579628 8695610 1495...

correct output
161906149

user output
161906149

Test 73

Verdict: ACCEPTED

input
16
16054161 19304150 57152778 337...

correct output
159099477

user output
159099477

Test 74

Verdict: ACCEPTED

input
16
71221723 14311522 45021194 426...

correct output
216877591

user output
216877591

Test 75

Verdict: ACCEPTED

input
16
10846316 79755467 74445718 590...

correct output
135548636

user output
135548636

Test 76

Verdict: ACCEPTED

input
16
51818372 6753746 10792121 3914...

correct output
164259241

user output
164259241

Test 77

Verdict: ACCEPTED

input
16
10755019 44179719 41876247 694...

correct output
133696572

user output
133696572

Test 78

Verdict: ACCEPTED

input
16
53567785 71579417 82569781 317...

correct output
150763443

user output
150763443

Test 79

Verdict: ACCEPTED

input
16
88623279 34185830 73137414 387...

correct output
198014364

user output
198014364

Test 80

Verdict: ACCEPTED

input
16
58343206 9110482 88825117 5032...

correct output
131581281

user output
131581281

Test 81

Verdict: ACCEPTED

input
16
36829570 59249556 69795996 491...

correct output
149993947

user output
149993947

Test 82

Verdict: ACCEPTED

input
16
55892938 61714751 75014144 212...

correct output
171851792

user output
171851792

Test 83

Verdict: ACCEPTED

input
16
53792259 75175740 86691312 687...

correct output
261201544

user output
261201544

Test 84

Verdict: ACCEPTED

input
16
83382234 98447679 33400623 580...

correct output
174166475

user output
174166475

Test 85

Verdict: ACCEPTED

input
16
49232089 54075676 50668211 720...

correct output
138328462

user output
138328462

Test 86

Verdict: ACCEPTED

input
16
29877190 8099586 92371257 8541...

correct output
103011096

user output
103011096

Test 87

Verdict: ACCEPTED

input
16
91519337 33138162 11320405 226...

correct output
148911385

user output
148911385

Test 88

Verdict: ACCEPTED

input
16
13035374 24654480 36933166 555...

correct output
141610494

user output
141610494

Test 89

Verdict: ACCEPTED

input
16
43339370 14613386 9518839 2982...

correct output
126679049

user output
126679049

Test 90

Verdict: ACCEPTED

input
16
9921885 71587757 22396864 1673...

correct output
139350643

user output
139350643