CSES - Aalto Competitive Programming 2025 - wk5 - Mon

Submission details
Task:	Kindergarten
Sender:	aalto25g_004
Submission time:	2025-09-30 22:25:00 +0300
Language:	C++ (C++17)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	ACCEPTED	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.00 s	details
#10	ACCEPTED	0.00 s	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	ACCEPTED	0.00 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	ACCEPTED	0.00 s	details
#17	ACCEPTED	0.00 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.00 s	details
#20	ACCEPTED	0.00 s	details
#21	ACCEPTED	0.01 s	details
#22	ACCEPTED	0.01 s	details
#23	ACCEPTED	0.01 s	details
#24	ACCEPTED	0.01 s	details
#25	ACCEPTED	0.01 s	details
#26	ACCEPTED	0.01 s	details
#27	ACCEPTED	0.01 s	details
#28	ACCEPTED	0.01 s	details
#29	ACCEPTED	0.01 s	details
#30	ACCEPTED	0.01 s	details
#31	ACCEPTED	0.72 s	details
#32	ACCEPTED	0.72 s	details
#33	ACCEPTED	0.72 s	details
#34	ACCEPTED	0.72 s	details
#35	ACCEPTED	0.72 s	details
#36	ACCEPTED	0.72 s	details
#37	ACCEPTED	0.72 s	details
#38	ACCEPTED	0.72 s	details
#39	ACCEPTED	0.72 s	details
#40	ACCEPTED	0.72 s	details
#41	ACCEPTED	0.72 s	details
#42	ACCEPTED	0.72 s	details
#43	ACCEPTED	0.72 s	details
#44	ACCEPTED	0.72 s	details
#45	ACCEPTED	0.72 s	details
#46	ACCEPTED	0.72 s	details
#47	ACCEPTED	0.72 s	details
#48	ACCEPTED	0.72 s	details
#49	ACCEPTED	0.72 s	details
#50	ACCEPTED	0.72 s	details
#51	ACCEPTED	0.72 s	details
#52	ACCEPTED	0.72 s	details
#53	ACCEPTED	0.72 s	details
#54	ACCEPTED	0.72 s	details
#55	ACCEPTED	0.72 s	details
#56	ACCEPTED	0.72 s	details
#57	ACCEPTED	0.72 s	details
#58	ACCEPTED	0.73 s	details
#59	ACCEPTED	0.72 s	details
#60	ACCEPTED	0.72 s	details
#61	ACCEPTED	0.72 s	details
#62	ACCEPTED	0.72 s	details
#63	ACCEPTED	0.72 s	details
#64	ACCEPTED	0.72 s	details
#65	ACCEPTED	0.72 s	details
#66	ACCEPTED	0.72 s	details
#67	ACCEPTED	0.72 s	details
#68	ACCEPTED	0.72 s	details
#69	ACCEPTED	0.72 s	details
#70	ACCEPTED	0.72 s	details
#71	ACCEPTED	0.72 s	details
#72	ACCEPTED	0.72 s	details
#73	ACCEPTED	0.72 s	details
#74	ACCEPTED	0.72 s	details
#75	ACCEPTED	0.72 s	details
#76	ACCEPTED	0.72 s	details
#77	ACCEPTED	0.72 s	details
#78	ACCEPTED	0.72 s	details
#79	ACCEPTED	0.72 s	details
#80	ACCEPTED	0.72 s	details
#81	ACCEPTED	0.72 s	details
#82	ACCEPTED	0.72 s	details
#83	ACCEPTED	0.72 s	details
#84	ACCEPTED	0.72 s	details
#85	ACCEPTED	0.72 s	details
#86	ACCEPTED	0.72 s	details
#87	ACCEPTED	0.72 s	details
#88	ACCEPTED	0.72 s	details
#89	ACCEPTED	0.72 s	details
#90	ACCEPTED	0.72 s	details

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 17;
long long result = 1e18;
long long n;
long long a[MAXN][MAXN];
long long check[MAXN];

struct PairHash {
    template <typename T1, typename T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

unordered_map<pair<int, int>, long long, PairHash> memo;

long long backtracking(long long i, long long depth, long long ans, int mask) {
    if (depth == n) return ans;
    
    auto key = make_pair(mask, i);
    if (memo.find(key) != memo.end()) return ans + memo[key];
    
    long long best = 1e18;
    for (int j = 1; j <= n; j++) {
        if (!(mask & (1 << j))) { 
            best = min(best, backtracking(j, depth + 1, ans + a[i][j], mask | (1 << j)));
        }
    }
    
    memo[key] = best - ans; 
    return best;
}

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

    for(int i = 1; i <= n; i++) {
        int mask = (1 << i);
        result = min(result, backtracking(i, 1, a[i][i], mask));
    }
    
    cout << result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`1 6` view save

correct output
`0` view save

user output
`6` view save

Test 2

Verdict: ACCEPTED

input
`1 4` view save

correct output
`0` view save

user output
`4` view save

Test 3

Verdict: ACCEPTED

input
`2 4 0 0 10` view save

correct output
`0` view save

user output
`4` view save

Test 4

Verdict: ACCEPTED

input
`2 6 7 7 9` view save

correct output
`7` view save

user output
`13` view save

Test 5

Verdict: ACCEPTED

input
`3 10 1 7 1 10 6 7 6 7` view save

correct output
`7` view save

user output
`14` view save

Test 6

Verdict: ACCEPTED

input
`3 2 9 10 9 2 10 10 10 5` view save

correct output
`19` view save

user output
`21` view save

Test 7

Verdict: ACCEPTED

input
`3 9 2 0 2 9 4 0 4 1` view save

correct output
`2` view save

user output
`3` view save

Test 8

Verdict: ACCEPTED

input
`4 0 4 10 5 4 10 3 0 10 3 5 0 5 0 0 4` view save

correct output
`4` view save

user output
`4` view save

Test 9

Verdict: ACCEPTED

input
`4 9 9 2 4 9 4 4 8 2 4 0 4 4 8 4 4` view save

correct output
`10` view save

user output
`14` view save

Test 10

Verdict: ACCEPTED

input
`4 0 5 1 4 5 0 0 1 1 0 2 2 4 1 2 1` view save

correct output
`2` view save

user output
`2` view save

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 ...` view save

correct output
`5` view save

user output
`6` view save

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 ...` view save

correct output
`3` view save

user output
`8` view save

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 ...` view save

correct output
`7` view save

user output
`8` view save

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 ...` view save

correct output
`11` view save

user output
`11` view save

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 ...` view save

correct output
`13` view save

user output
`17` view save

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 ...` view save

correct output
`5` view save

user output
`8` view save

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 ...` view save

correct output
`15` view save

user output
`16` view save

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 ...` view save

correct output
`13` view save

user output
`17` view save

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 ...` view save

correct output
`10` view save

user output
`12` view save

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 ...` view save

correct output
`12` view save

user output
`14` view save

Test 21

Verdict: ACCEPTED

input
`10 549 646 792 87 979 640 264 618...` view save

correct output
`1257` view save

user output
`1718` view save

Test 22

Verdict: ACCEPTED

input
`10 417 92 419 671 801 895 98 315 ...` view save

correct output
`1093` view save

user output
`1185` view save

Test 23

Verdict: ACCEPTED

input
`10 436 330 621 786 505 597 468 38...` view save

correct output
`1912` view save

user output
`2159` view save

Test 24

Verdict: ACCEPTED

input
`10 551 897 29 591 283 781 976 92 ...` view save

correct output
`1530` view save

user output
`1548` view save

Test 25

Verdict: ACCEPTED

input
`10 967 216 780 597 436 75 528 545...` view save

correct output
`1166` view save

user output
`1274` view save

Test 26

Verdict: ACCEPTED

input
`10 222 612 80 274 600 144 24 578 ...` view save

correct output
`1310` view save

user output
`1468` view save

Test 27

Verdict: ACCEPTED

input
`10 893 595 438 991 54 541 717 718...` view save

correct output
`1942` view save

user output
`2051` view save

Test 28

Verdict: ACCEPTED

input
`10 76 539 679 910 601 133 205 838...` view save

correct output
`2202` view save

user output
`2428` view save

Test 29

Verdict: ACCEPTED

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

correct output
`987` view save

user output
`1114` view save

Test 30

Verdict: ACCEPTED

input
`10 10 218 166 573 386 804 650 874...` view save

correct output
`1545` view save

user output
`1730` view save

Test 31

Verdict: ACCEPTED

input
`16 78876117 17293464 73807511 451...` view save

correct output
`141535044` view save

user output
`163542284` view save

Test 32

Verdict: ACCEPTED

input
`16 18434581 96310208 2094677 8835...` view save

correct output
`217719706` view save

user output
`238606282` view save

Test 33

Verdict: ACCEPTED

input
`16 15764865 97858716 92778181 718...` view save

correct output
`167604914` view save

user output
`173079673` view save

Test 34

Verdict: ACCEPTED

input
`16 79528724 65612103 26207475 638...` view save

correct output
`140515513` view save

user output
`164541958` view save

Test 35

Verdict: ACCEPTED

input
`16 52556424 55139192 95364389 546...` view save

correct output
`140013397` view save

user output
`155417091` view save

Test 36

Verdict: ACCEPTED

input
`16 86801053 11426789 72187831 966...` view save

correct output
`93732738` view save

user output
`122238144` view save

Test 37

Verdict: ACCEPTED

input
`16 22833997 7191499 71236196 3216...` view save

correct output
`115026040` view save

user output
`122208874` view save

Test 38

Verdict: ACCEPTED

input
`16 30132775 3994617 56422716 4279...` view save

correct output
`122521730` view save

user output
`130410491` view save

Test 39

Verdict: ACCEPTED

input
`16 66508002 86884113 88110850 970...` view save

correct output
`206680250` view save

user output
`216648084` view save

Test 40

Verdict: ACCEPTED

input
`16 9973896 65003382 54473078 6575...` view save

correct output
`105290977` view save

user output
`123804573` view save

Test 41

Verdict: ACCEPTED

input
`16 60142917 67282857 11933232 463...` view save

correct output
`149892373` view save

user output
`158432281` view save

Test 42

Verdict: ACCEPTED

input
`16 4982660 31508124 77610451 9338...` view save

correct output
`208191625` view save

user output
`215026352` view save

Test 43

Verdict: ACCEPTED

input
`16 21317409 22538814 78950075 437...` view save

correct output
`141684927` view save

user output
`146682576` view save

Test 44

Verdict: ACCEPTED

input
`16 52899464 63202728 6654687 1447...` view save

correct output
`162046504` view save

user output
`173025558` view save

Test 45

Verdict: ACCEPTED

input
`16 98172450 57262621 54713540 967...` view save

correct output
`151356452` view save

user output
`163024094` view save

Test 46

Verdict: ACCEPTED

input
`16 88979873 56880637 33342355 868...` view save

correct output
`159671124` view save

user output
`179900219` view save

Test 47

Verdict: ACCEPTED

input
`16 31489774 75583422 98416671 495...` view save

correct output
`177673400` view save

user output
`202643931` view save

Test 48

Verdict: ACCEPTED

input
`16 43534750 41244279 21038793 242...` view save

correct output
`174069522` view save

user output
`185809216` view save

Test 49

Verdict: ACCEPTED

input
`16 74549766 97697405 65731362 223...` view save

correct output
`164091596` view save

user output
`164563085` view save

Test 50

Verdict: ACCEPTED

input
`16 88329068 78556994 29213132 737...` view save

correct output
`150948961` view save

user output
`188135376` view save

Test 51

Verdict: ACCEPTED

input
`16 11868309 52454190 2188140 3426...` view save

correct output
`145704982` view save

user output
`159246240` view save

Test 52

Verdict: ACCEPTED

input
`16 62601211 24407904 38967625 742...` view save

correct output
`165774974` view save

user output
`175475530` view save

Test 53

Verdict: ACCEPTED

input
`16 38353763 90537037 98227382 885...` view save

correct output
`128735723` view save

user output
`150314603` view save

Test 54

Verdict: ACCEPTED

input
`16 87124995 71164598 85140576 178...` view save

correct output
`88146905` view save

user output
`115349220` view save

Test 55

Verdict: ACCEPTED

input
`16 15506055 73736552 44372116 853...` view save

correct output
`139764802` view save

user output
`160396968` view save

Test 56

Verdict: ACCEPTED

input
`16 20052620 55628826 15868440 899...` view save

correct output
`112678656` view save

user output
`126913914` view save

Test 57

Verdict: ACCEPTED

input
`16 38365166 78120078 30444983 287...` view save

correct output
`180080436` view save

user output
`194589072` view save

Test 58

Verdict: ACCEPTED

input
`16 46161809 99247781 74790752 906...` view save

correct output
`192231810` view save

user output
`198948145` view save

Test 59

Verdict: ACCEPTED

input
`16 96396611 61707575 39771927 957...` view save

correct output
`157075200` view save

user output
`188833153` view save

Test 60

Verdict: ACCEPTED

input
`16 86701456 19718778 48320555 202...` view save

correct output
`171350081` view save

user output
`193269013` view save

Test 61

Verdict: ACCEPTED

input
`16 10218362 40742172 91128924 285...` view save

correct output
`127429234` view save

user output
`141011780` view save

Test 62

Verdict: ACCEPTED

input
`16 79903579 1974104 24354885 4902...` view save

correct output
`119531862` view save

user output
`129886482` view save

Test 63

Verdict: ACCEPTED

input
`16 23816783 24638719 49178170 814...` view save

correct output
`161233528` view save

user output
`163515079` view save

Test 64

Verdict: ACCEPTED

input
`16 22336543 34284046 7826114 4407...` view save

correct output
`172344121` view save

user output
`181653194` view save

Test 65

Verdict: ACCEPTED

input
`16 4933488 53040995 75121239 3334...` view save

correct output
`150345908` view save

user output
`156982990` view save

Test 66

Verdict: ACCEPTED

input
`16 15740195 82161403 83343605 558...` view save

correct output
`177299100` view save

user output
`196233096` view save

Test 67

Verdict: ACCEPTED

input
`16 3639374 43311419 10627086 4629...` view save

correct output
`181883199` view save

user output
`182014934` view save

Test 68

Verdict: ACCEPTED

input
`16 10600561 29567300 26714920 537...` view save

correct output
`153201253` view save

user output
`165235192` view save

Test 69

Verdict: ACCEPTED

input
`16 34181158 4262559 25064528 1281...` view save

correct output
`110754397` view save

user output
`110836544` view save

Test 70

Verdict: ACCEPTED

input
`16 1379850 55703817 5455026 69880...` view save

correct output
`150243591` view save

user output
`163312020` view save

Test 71

Verdict: ACCEPTED

input
`16 69328497 20779089 35701876 660...` view save

correct output
`163180293` view save

user output
`172114857` view save

Test 72

Verdict: ACCEPTED

input
`16 11384815 61579628 8695610 1495...` view save

correct output
`161906149` view save

user output
`171654691` view save

Test 73

Verdict: ACCEPTED

input
`16 16054161 19304150 57152778 337...` view save

correct output
`159099477` view save

user output
`181038010` view save

Test 74

Verdict: ACCEPTED

input
`16 71221723 14311522 45021194 426...` view save

correct output
`216877591` view save

user output
`221335303` view save

Test 75

Verdict: ACCEPTED

input
`16 10846316 79755467 74445718 590...` view save

correct output
`135548636` view save

user output
`141728193` view save

Test 76

Verdict: ACCEPTED

input
`16 51818372 6753746 10792121 3914...` view save

correct output
`164259241` view save

user output
`197208257` view save

Test 77

Verdict: ACCEPTED

input
`16 10755019 44179719 41876247 694...` view save

correct output
`133696572` view save

user output
`144596378` view save

Test 78

Verdict: ACCEPTED

input
`16 53567785 71579417 82569781 317...` view save

correct output
`150763443` view save

user output
`168999706` view save

Test 79

Verdict: ACCEPTED

input
`16 88623279 34185830 73137414 387...` view save

correct output
`198014364` view save

user output
`199496366` view save

Test 80

Verdict: ACCEPTED

input
`16 58343206 9110482 88825117 5032...` view save

correct output
`131581281` view save

user output
`146519503` view save

Test 81

Verdict: ACCEPTED

input
`16 36829570 59249556 69795996 491...` view save

correct output
`149993947` view save

user output
`172416774` view save

Test 82

Verdict: ACCEPTED

input
`16 55892938 61714751 75014144 212...` view save

correct output
`171851792` view save

user output
`190815832` view save

Test 83

Verdict: ACCEPTED

input
`16 53792259 75175740 86691312 687...` view save

correct output
`261201544` view save

user output
`283834584` view save

Test 84

Verdict: ACCEPTED

input
`16 83382234 98447679 33400623 580...` view save

correct output
`174166475` view save

user output
`222578957` view save

Test 85

Verdict: ACCEPTED

input
`16 49232089 54075676 50668211 720...` view save

correct output
`138328462` view save

user output
`155425882` view save

Test 86

Verdict: ACCEPTED

input
`16 29877190 8099586 92371257 8541...` view save

correct output
`103011096` view save

user output
`114686861` view save

Test 87

Verdict: ACCEPTED

input
`16 91519337 33138162 11320405 226...` view save

correct output
`148911385` view save

user output
`153913544` view save

Test 88

Verdict: ACCEPTED

input
`16 13035374 24654480 36933166 555...` view save

correct output
`141610494` view save

user output
`154645868` view save

Test 89

Verdict: ACCEPTED

input
`16 43339370 14613386 9518839 2982...` view save

correct output
`126679049` view save

user output
`138944084` view save

Test 90

Verdict: ACCEPTED

input
`16 9921885 71587757 22396864 1673...` view save

correct output
`139350643` view save

user output
`140039803` view save

Aalto Competitive Programming 2025 - wk5 - Mon

Kindergarten

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Test 70

Test 71

Test 72

Test 73

Test 74

Test 75

Test 76