Submission #24215199

---

Source Code Expand

def init(i):
    return X[i]
def merge(s, x, y):
    return max(s, x + y)
def fin(i, s):
    return s

n = int(input())
A = [[int(a) for a in input().split()] for _ in range(n)]
X = [0] * (1 << n)
for i in range(1, 1 << n):
    L = []
    for j in range(n):
        if i >> j & 1:
            L.append(j)
    s = 0
    for j, a in enumerate(L):
        for k in range(j):
            b = L[k]
            s += A[a][b]
    X[i] = s
    
Y = [0] * (1 << n)
for i in range(1, 1 << n):
    j = (i - 1) & i
    s = init(i)
    while j:
        s = merge(s, X[i^j], Y[j])
        j = (j - 1) & i
    
    Y[i] = fin(i, s)
    
print(Y[-1])

Submission Info

Judge Result