CSES - Aalto Competitive Programming 2024 - wk5 - Mon - Results
Submission details
Task:Kindergarten
Sender:aalto2024e_001
Submission time:2024-09-30 16:50:10 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#18ACCEPTED0.01 sdetails
#19ACCEPTED0.01 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.01 sdetails
#24ACCEPTED0.01 sdetails
#25ACCEPTED0.01 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.01 sdetails
#28ACCEPTED0.01 sdetails
#29ACCEPTED0.01 sdetails
#30ACCEPTED0.01 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.05 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 <algorithm>
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define int long long

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 16;

int n, r[N][N], dp[1 << N][N];

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> r[i][j];
        }
    }

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

    for (int msk = 0; msk < (1 << n); msk++) {
        for (int who = 0; who < n; who++) {
            if (msk >> who & 1) {
                for (int lst = 0; lst < n; lst++) {
                    if (lst != who && (msk >> lst & 1)) {
                        dp[msk][who] = min(dp[msk][who], dp[msk ^ (1 << who)][lst] + r[lst][who]);
                    }
                }
            }
        }
    }

    int ans = 1e18;
    int all = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[all][i]);
    }

    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
            
    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}

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