Submission #3978631

Source Code Expand

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

V = [0]*(1 << N)
for s in range(1 << N):
    r = 0
    for i, Ai in enumerate(A):
        if not s & (1 << i):
            continue
        for j in range(i+1, N):
            if not s & (1 << j):
                continue
            r += Ai[j]
    V[s] = r

U = [-10**10]*(1 << N)
U[(1 << N) - 1] = 0
for state in range((1 << N)-1, 0, -1):
    s = state
    v = U[state]
    while s:
        s = (s - 1) & state
        U[s] = max(U[s], v + V[state ^ s])
print(U[0])

Submission Info

Submission Time
Task U - Grouping
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 564 Byte
Status AC
Exec Time 881 ms
Memory 45020 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 24
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19
Case Name Status Exec Time Memory
0_00 AC 163 ms 38256 KiB
0_01 AC 162 ms 38256 KiB
0_02 AC 169 ms 38256 KiB
0_03 AC 873 ms 45020 KiB
1_00 AC 164 ms 38384 KiB
1_01 AC 851 ms 44380 KiB
1_02 AC 529 ms 43740 KiB
1_03 AC 556 ms 43996 KiB
1_04 AC 569 ms 44764 KiB
1_05 AC 565 ms 44764 KiB
1_06 AC 577 ms 44764 KiB
1_07 AC 564 ms 44764 KiB
1_08 AC 562 ms 44380 KiB
1_09 AC 862 ms 44764 KiB
1_10 AC 573 ms 44508 KiB
1_11 AC 561 ms 44508 KiB
1_12 AC 863 ms 44508 KiB
1_13 AC 859 ms 44764 KiB
1_14 AC 881 ms 44764 KiB
1_15 AC 864 ms 44764 KiB
1_16 AC 563 ms 44764 KiB
1_17 AC 560 ms 44508 KiB
1_18 AC 867 ms 44764 KiB
1_19 AC 568 ms 44764 KiB