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

Code

import sys

def minimal_rivalry_sum(n, rivalry):
    INF = sys.maxsize
    dp = [[INF] * n for _ in range(1 << n)]
    
    for i in range(n):
        dp[1 << i][i] = 0

    for mask in range(1 << n):
        for u in range(n):
            if mask & (1 << u):  
                for v in range(n):
                    if not (mask & (1 << v)):  
                        new_mask = mask | (1 << v)
                        dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + rivalry[u][v])

    all_kids_visited = (1 << n) - 1
    result = min(dp[all_kids_visited][i] for i in range(n))
    
    return result

# Input
n = int(input())
rivalry_matrix = [list(map(int, input().split())) for _ in range(n)]

print(minimal_rivalry_sum(n, rivalry_matrix))

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:

input
16
78876117 17293464 73807511 451...

correct output
141535044

user output
(empty)

Test 32

Verdict:

input
16
18434581 96310208 2094677 8835...

correct output
217719706

user output
(empty)

Test 33

Verdict:

input
16
15764865 97858716 92778181 718...

correct output
167604914

user output
(empty)

Test 34

Verdict:

input
16
79528724 65612103 26207475 638...

correct output
140515513

user output
(empty)

Test 35

Verdict:

input
16
52556424 55139192 95364389 546...

correct output
140013397

user output
(empty)

Test 36

Verdict:

input
16
86801053 11426789 72187831 966...

correct output
93732738

user output
(empty)

Test 37

Verdict:

input
16
22833997 7191499 71236196 3216...

correct output
115026040

user output
(empty)

Test 38

Verdict:

input
16
30132775 3994617 56422716 4279...

correct output
122521730

user output
(empty)

Test 39

Verdict:

input
16
66508002 86884113 88110850 970...

correct output
206680250

user output
(empty)

Test 40

Verdict:

input
16
9973896 65003382 54473078 6575...

correct output
105290977

user output
(empty)

Test 41

Verdict:

input
16
60142917 67282857 11933232 463...

correct output
149892373

user output
(empty)

Test 42

Verdict:

input
16
4982660 31508124 77610451 9338...

correct output
208191625

user output
(empty)

Test 43

Verdict:

input
16
21317409 22538814 78950075 437...

correct output
141684927

user output
(empty)

Test 44

Verdict:

input
16
52899464 63202728 6654687 1447...

correct output
162046504

user output
(empty)

Test 45

Verdict:

input
16
98172450 57262621 54713540 967...

correct output
151356452

user output
(empty)

Test 46

Verdict:

input
16
88979873 56880637 33342355 868...

correct output
159671124

user output
(empty)

Test 47

Verdict:

input
16
31489774 75583422 98416671 495...

correct output
177673400

user output
(empty)

Test 48

Verdict:

input
16
43534750 41244279 21038793 242...

correct output
174069522

user output
(empty)

Test 49

Verdict:

input
16
74549766 97697405 65731362 223...

correct output
164091596

user output
(empty)

Test 50

Verdict:

input
16
88329068 78556994 29213132 737...

correct output
150948961

user output
(empty)

Test 51

Verdict:

input
16
11868309 52454190 2188140 3426...

correct output
145704982

user output
(empty)

Test 52

Verdict:

input
16
62601211 24407904 38967625 742...

correct output
165774974

user output
(empty)

Test 53

Verdict:

input
16
38353763 90537037 98227382 885...

correct output
128735723

user output
(empty)

Test 54

Verdict:

input
16
87124995 71164598 85140576 178...

correct output
88146905

user output
(empty)

Test 55

Verdict:

input
16
15506055 73736552 44372116 853...

correct output
139764802

user output
(empty)

Test 56

Verdict:

input
16
20052620 55628826 15868440 899...

correct output
112678656

user output
(empty)

Test 57

Verdict:

input
16
38365166 78120078 30444983 287...

correct output
180080436

user output
(empty)

Test 58

Verdict:

input
16
46161809 99247781 74790752 906...

correct output
192231810

user output
(empty)

Test 59

Verdict:

input
16
96396611 61707575 39771927 957...

correct output
157075200

user output
(empty)

Test 60

Verdict:

input
16
86701456 19718778 48320555 202...

correct output
171350081

user output
(empty)

Test 61

Verdict:

input
16
10218362 40742172 91128924 285...

correct output
127429234

user output
(empty)

Test 62

Verdict:

input
16
79903579 1974104 24354885 4902...

correct output
119531862

user output
(empty)

Test 63

Verdict:

input
16
23816783 24638719 49178170 814...

correct output
161233528

user output
(empty)

Test 64

Verdict:

input
16
22336543 34284046 7826114 4407...

correct output
172344121

user output
(empty)

Test 65

Verdict:

input
16
4933488 53040995 75121239 3334...

correct output
150345908

user output
(empty)

Test 66

Verdict:

input
16
15740195 82161403 83343605 558...

correct output
177299100

user output
(empty)

Test 67

Verdict:

input
16
3639374 43311419 10627086 4629...

correct output
181883199

user output
(empty)

Test 68

Verdict:

input
16
10600561 29567300 26714920 537...

correct output
153201253

user output
(empty)

Test 69

Verdict:

input
16
34181158 4262559 25064528 1281...

correct output
110754397

user output
(empty)

Test 70

Verdict:

input
16
1379850 55703817 5455026 69880...

correct output
150243591

user output
(empty)

Test 71

Verdict:

input
16
69328497 20779089 35701876 660...

correct output
163180293

user output
(empty)

Test 72

Verdict:

input
16
11384815 61579628 8695610 1495...

correct output
161906149

user output
(empty)

Test 73

Verdict:

input
16
16054161 19304150 57152778 337...

correct output
159099477

user output
(empty)

Test 74

Verdict:

input
16
71221723 14311522 45021194 426...

correct output
216877591

user output
(empty)

Test 75

Verdict:

input
16
10846316 79755467 74445718 590...

correct output
135548636

user output
(empty)

Test 76

Verdict:

input
16
51818372 6753746 10792121 3914...

correct output
164259241

user output
(empty)

Test 77

Verdict:

input
16
10755019 44179719 41876247 694...

correct output
133696572

user output
(empty)

Test 78

Verdict:

input
16
53567785 71579417 82569781 317...

correct output
150763443

user output
(empty)

Test 79

Verdict:

input
16
88623279 34185830 73137414 387...

correct output
198014364

user output
(empty)

Test 80

Verdict:

input
16
58343206 9110482 88825117 5032...

correct output
131581281

user output
(empty)

Test 81

Verdict:

input
16
36829570 59249556 69795996 491...

correct output
149993947

user output
(empty)

Test 82

Verdict:

input
16
55892938 61714751 75014144 212...

correct output
171851792

user output
(empty)

Test 83

Verdict:

input
16
53792259 75175740 86691312 687...

correct output
261201544

user output
(empty)

Test 84

Verdict:

input
16
83382234 98447679 33400623 580...

correct output
174166475

user output
(empty)

Test 85

Verdict:

input
16
49232089 54075676 50668211 720...

correct output
138328462

user output
(empty)

Test 86

Verdict:

input
16
29877190 8099586 92371257 8541...

correct output
103011096

user output
(empty)

Test 87

Verdict:

input
16
91519337 33138162 11320405 226...

correct output
148911385

user output
(empty)

Test 88

Verdict:

input
16
13035374 24654480 36933166 555...

correct output
141610494

user output
(empty)

Test 89

Verdict:

input
16
43339370 14613386 9518839 2982...

correct output
126679049

user output
(empty)

Test 90

Verdict:

input
16
9921885 71587757 22396864 1673...

correct output
139350643

user output
(empty)