Submission #53254287

Source Code Expand

N = int(input())
D = [[0]*N for _ in range(N)]
for i in range(N - 1):
    d = list(map(int, input().split()))
    for j in range(N - i - 1):
        D[i][i + j + 1] = d[j]

dp = [0]*(1 << N)
for S in range(1 << N):
    for i in range(N):
        for j in range(i + 1, N):
            if (S >> i) & 1:
                continue
            if (S >> j) & 1:
                continue
            p = S
            p |= (1 << i)
            p |= (1 << j)
            dp[p] = max(dp[p], dp[S] + D[i][j])

print(dp[-1])

Submission Info

Submission Time
Task D - General Weighted Max Matching
User ryusuke_h
Language Python (PyPy 3.10-v7.3.12)
Score 400
Code Size 532 Byte
Status AC
Exec Time 139 ms
Memory 83592 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 20
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 56 ms 76496 KiB
00_sample_02.txt AC 55 ms 76496 KiB
00_sample_03.txt AC 132 ms 83148 KiB
01_test_01.txt AC 55 ms 76484 KiB
01_test_02.txt AC 139 ms 83296 KiB
01_test_03.txt AC 135 ms 83084 KiB
01_test_04.txt AC 134 ms 83440 KiB
01_test_05.txt AC 106 ms 82316 KiB
01_test_06.txt AC 106 ms 82180 KiB
01_test_07.txt AC 135 ms 83160 KiB
01_test_08.txt AC 106 ms 82140 KiB
01_test_09.txt AC 133 ms 83296 KiB
01_test_10.txt AC 137 ms 83200 KiB
01_test_11.txt AC 105 ms 82076 KiB
01_test_12.txt AC 133 ms 83388 KiB
01_test_13.txt AC 134 ms 83592 KiB
01_test_14.txt AC 131 ms 83296 KiB
01_test_15.txt AC 106 ms 82044 KiB
01_test_16.txt AC 134 ms 83372 KiB
01_test_17.txt AC 104 ms 81968 KiB