Problem:
 Score : 100 points    Problem Statement There are N rabbits, numbered 1, 2, \ldots, N .  For each i, j ( 1 \leq i, j \leq N ), the compatibility of Rabbit i and j is described by an integer a_{i, j} .
Here, a_{i, i} = 0 for each i ( 1 \leq i \leq N ), and a_{i, j} = a_{j, i} for each i and j ( 1 \leq i, j \leq N ).  Taro is dividing the N rabbits into some number of groups.
Here, each rabbit must belong to exactly one group.
After grouping, for each i and j ( 1 \leq i < j \leq N ), Taro earns a_{i, j} points if Rabbit i and j belong to the same group.  Find Taro's maximum possible total score.      Constraints  All values in input are integers.  1 \leq N \leq 16  |a_{i, j}| \leq 10^9  a_{i, i} = 0  a_{i, j} = a_{j, i}         Input Input is given from Standard Input in the following format:  N  a_{1, 1}  \ldots  a_{1, N}  :  a_{N, 1}  \ldots  a_{N, N}       Output Print Taro's maximum possible total score.        Sample Input 1 3
0 10 20
10 0 -100
20 -100 0      Sample Output 1 20  The rabbits should be divided as \{1, 3\}, \{2\} .       Sample Input 2 2
0 -10
-10 0      Sample Output 2 0  The rabbits should be divided as \{1\}, \{2\} .       Sample Input 3 4
0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000
1000000000 1000000000 0 -1
1000000000 1000000000 -1 0      Sample Output 3 4999999999  The rabbits should be divided as \{1, 2, 3, 4\} .
Note that the answer may not fit into a 32-bit integer type.       Sample Input 4 16
0 5 -4 -5 -8 -4 7 2 -4 0 7 0 2 -3 7 7
5 0 8 -9 3 5 2 -7 2 -7 0 -1 -4 1 -1 9
-4 8 0 -9 8 9 3 1 4 9 6 6 -6 1 8 9
-5 -9 -9 0 -7 6 4 -1 9 -3 -5 0 1 2 -4 1
-8 3 8 -7 0 -5 -9 9 1 -9 -6 -3 -8 3 4 3
-4 5 9 6 -5 0 -6 1 -2 2 0 -5 -2 3 1 2
7 2 3 4 -9 -6 0 -2 -2 -9 -3 9 -2 9 2 -5
2 -7 1 -1 9 1 -2 0 -6 0 -6 6 4 -1 -7 8
-4 2 4 9 1 -2 -2 -6 0 8 -6 -2 -4 8 7 7
0 -7 9 -3 -9 2 -9 0 8 0 0 1 -3 3 -6 -6
7 0 6 -5 -6 0 -3 -6 -6 0 0 5 7 -1 -5 3
0 -1 6 0 -3 -5 9 6 -2 1 5 0 -2 7 -8 0
2 -4 -6 1 -8 -2 -2 4 -4 -3 7 -2 0 -9 7 1
-3 1 1 2 3 3 9 -1 8 3 -1 7 -9 0 -6 -8
7 -1 8 -4 4 1 2 -7 7 -6 -5 -8 7 -6 0 -9
7 9 9 1 3 2 -5 8 7 -6 3 0 1 -8 -9 0      Sample Output 4 132

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
DP = []
for s in range(2**n):
    tmp = 0
    bit = bin(s)[2:].zfill(n)
    for i in range(n):
        for j in range(i + 1, n):
            if bit[i] == '1' and bit[j] == '1':
                tmp += A[i][j]
    msk = [i for i in range(n) if bit[i] == '1']
    DP.append(tmp)
    t = (s - 1) & s
    while t:
        DP[s] = max(DP[s], DP[t] + DP[s - t])
        t = (t - 1) & s
print(DP[-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    a = [list(map(int, rl().split())) for _ in range(N)]
    INF = 10 ** 18
    
    dp = [0] * 2 ** N
    searched = [False] * 2 ** N
    searched[0] = True
    c = [0] * 2 ** N
    
    for s in range(2 ** N):
        tmp = 0
        for i in range(N):
            if not s >> i & 1:
                continue
            for j in range(i + 1, N):
                if s >> j & 1:
                    tmp += a[i][j]
        c[s] = tmp
    
    def calc(S):
        if searched[S]:
            return dp[S]
        searched[S] = True
        
        res = -INF
        T = 2 ** N
        while 0 < T:
            T = (T - 1) & S
            res = max(res, c[T] + calc(S ^ T))
        dp[S] = res
        return res
    
    calc(2 ** N - 1)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Solution (Python):

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=[[0]*N for _ in range(N)]
    for i in range(N):
        a[i]=LI()
    MS=pow(2,N)
    
    dp=[0]*MS
    
    
    
    
    
    
    for S in range(1,MS):
        for j in range(N):
            if S>>j&1:
                dp[S]=dp[S-(1<<j)]
                for k in range(N):
                    if S>>k&1:
                        dp[S]+=a[j][k]
                break
            
    
    for S in range(1,MS):
        
        T=S
        while T:
            T=(T-1)&S
            dp[S]=max(dp[S],dp[T]+dp[S-T])
            
    print(dp[MS-1])
                        
    
main()

Solution (Python):

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
INF=-10**12
dp=[INF]*(1<<n)
def memo(s):
    if dp[s]>INF:
        return dp[s]
    ans=0
    for i in range(n-1):
        for j in range(i,n):
            if s>>i&1 and s>>j&1:
                ans+=a[i][j]
    
    
    t=(s-1)&s
    while t>0:
        ans=max(ans,memo(t)+memo(t^s))
        t=(t-1)&s
    dp[s]=ans
    return ans
print(memo((1<<n)-1))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    INF = 10**18+1
    memo = [-INF]*(1<<N)
    for i in range(N):
        memo[1<<i] = 0
    
    def point(x):
        if memo[x] != -INF:
            return memo[x]
        con = []
        for i in range(N):
            if (x>>i)&1:
                con.append(i)
        ret = 0
        for i in con:
            for j in con:
                ret += a[i][j]
        ret //= 2
        T = x
        while T > 0:
            T = (T-1)&x
            if T == 0:
                break
            ret = max(ret,point(T)+point(x^T))
        memo[x] = ret
        return ret

    print(point((1<<N)-1))
    
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dp = [-10**18 for i in range(1<<n)]
for i in range(n):
  dp[2**i] = 0
def judge(S):
  if dp[S] != -10**18:
    return dp[S]
  T = S
  retls = [0]
  sls = []
  ret0 = 0
  for i in range(n):
    if 1<<i & S:
      sls.append(i)
  for i,j in combinations(sls,2):
    ret0 += a[i][j]
  retls.append(ret0)
  while T>0:
    T = (T-1)&S
    if T == 0:
      break
    retls.append(judge(T)+judge(S^T))
  dp[S] = max(retls)
  return max(retls)
print(judge(2**n-1))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

table = [0] * (1 << N)
for k in range(1 << N):
  for i in range(N):
    for j in range(N):
      if (1 << i) & k and ((1 << j) & k):
        table[k] += a[i][j]
  table[k] //= 2

dp = [0] * (1 << N)
for i in range(1 << N):
  j = i
  dp[i] = table[i]
  while j > 0:
    dp[i] = max(dp[i], dp[j] + table[i - j])
    j = (j - 1) & i
print(dp[-1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mi = [0]*(1 << n)
for bit in range(1 << n):
  for i in range(n-1):
    if bit & (1 << i):
      for j in range(i+1, n):
        if bit & (1 << j):
          mi[bit] += a[i][j]
for bit in range(1 << n):
  v = bit
  while v > (bit//2):
    if mi[bit] < mi[v] + mi[bit^v]:
      mi[bit] = mi[v] + mi[bit^v]
    v = (v-1) & bit
print(mi[-1])

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




point = [0] * (2**N)
for mask in range(2**N):
  mask_str = bin(mask)[2:].zfill(N)
  for i in range(N):
    if mask_str[i] == '1':
      for j in range(i+1, N):
        if mask_str[j] == '1':
          point[mask] += A[i][j]







dp = [-10**19 * 16] * (2**N)
dp[0] = 0
for mask in range(1, 2**N):
  dp[mask] = point[mask] 
  _mask = (mask-1) & mask 
  while _mask > 0:
    dp[mask] = max(dp[mask], dp[mask^_mask] + point[_mask]) 
    _mask = (_mask-1) & mask 


print(dp[-1])

Solution (Python):
n=int(input())
A=[list(map(int,input().split()))for _ in range(n)]

S=[0]*(1<<n)
for i in range(1<<n):
    for j in range(n):
        if i&(1<<j):
            for k in range(n):
                if i&(1<<k):
                    S[i]+=A[j][k]
dp=[-10**9]*(1<<n)
dp[0]=0
for i in range(1,1<<n):
    j=i
    b=i.bit_length()
    while j.bit_length()==b:
        dp[i]=max(dp[i],S[j]+dp[i-j])
        j=i&(j-1)
print(dp[-1]//2)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

mask = 1<<n
group = [0]*mask
for i in range(mask):
    for j in range(n):
        for k in range(n):
            if (i>>j)&(i>>k)&1:
                group[i] += a[j][k]
    group[i] //= 2

DP = group[:]
for state in range(1, mask):
    j = (state-1)&state
    while j:
        k = state^j
        DP[state] = max(DP[state], DP[j]+DP[k])
        j = (j-1)&state

print(DP[-1])

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

max_mask = 1<<n
DP = [0]*max_mask

for state in range(1, max_mask):
    flag = []
    for i in range(n):
        if (state>>i)&1:
            flag.append(i)
    tmp = 0
    for i in flag:
        for j in flag:
            tmp += a[i][j]
    DP[state] = tmp//2

    j = (state-1)&state
    while j:
        k = state^j
        DP[state] = max(DP[state], DP[j]+DP[k])
        j = (j-1)&state
print(DP[-1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

n_bit = 2**n


flag_num = {}
log2_num = {}
for i in range(n+1):
    flag_num[i] = []
    log2_num[2**i] = i

for i in range(n_bit):
    num = str(bin(i)).count('1')
    flag_num[num].append(i)





g = [0]*n_bit
for i in range(2,n+1):
    for j in flag_num[i]:
        
        left_flag = j & (-j)
        
        right_flags = j - left_flag

        g[j] = g[right_flags]
        left = log2_num[left_flag]
        for k in range(n+1):
            if( ((right_flags >> k) & 1)  > 0):
                g[j] += a[left][k]


init = -1 * 150 * 10**10
dp = [init] * n_bit
dp[0] = 0
for i in range(1,n+1):
    for j in flag_num[i]:
        temp = init
        k = (j-1) & j
        while( k >= 0):
            
            temp = max(temp, dp[k] + g[j-k] )

            
            if(k==0):
                break
            
            k = (k-1) & j
        dp[j] = temp

print(dp[n_bit - 1])

Solution (Python):
n=int(input());a=[list(map(int,input().split()))for i in range(n)];t=[0]*(1<<n)
for i in range(1,1<<n):
    p=i&(i-1)
    t[i]=sum([sum([a[j][h]for h in range(n)if 1<<h&i])for j in range(n)if 1<<j&i])
    while p:
        t[i]=max(t[i],t[p]+t[i^p])
        p=(p-1)&i
print(t[-1]//2)

Solution (Python):
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]
t=[0]*(1<<n)
for i in range(1,1<<n):
    p=i&(i-1)
    g=sum([sum([a[j][h]for h in range(n) if 1<<h&i])for j in range(n)if 1<<j&i])
    while p:
        g=max(g,t[p]+t[i^p])
        p=(p-1)&i
    t[i]=g
print(t[-1]//2)

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))

    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1

    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod

    ans = dp[N][K]%mod
    print(ans)
    return

def examN():
    N = I()
    A = LI()
    cumA = [0]*(N+1)
    for i in range(N):
        cumA[i+1] = cumA[i]+A[i]
    dp = [[inf]*(N) for _ in range(N)]
    for i in range(N):
        dp[0][i] = 0
    for i in range(N-1):
        for j in range(N-i-1):
            for k in range(i+1):
                cur = dp[i-k][j+k+1]+dp[k][j]+cumA[i+j+2]-cumA[j]
                dp[i+1][j] = min(dp[i+1][j],cur)

    ans = dp[N-1][0]
    print(ans)
    return

def examO():
    N = I()
    A = [LI() for _ in range(N)]
    loop = 2**N
    dp = [[0]*loop for _ in range(N+1)]
    dp[0][0] = 1
    for mask in range(loop):
        cur = 0
        for j in range(N):
            if mask&(1<<j)==(1<<j):
                cur +=1
        for i in range(N):
            if mask&(1<<i)==0 and A[i][cur]==1:
                dp[cur+1][mask|(1<<i)] += dp[cur][mask]
                dp[cur + 1][mask | (1 << i)] %=mod

    ans = dp[N][loop-1]
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
            W %= mod
            B %= mod

        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%mod)
    return

def examQ():
    N = I()
    H = LI()
    maxH = max(H)
    A = LI()
    dp = [0](maxH+1)
    cur = 0
    for i in range(N):
        dp[B[i]] = cur+dp[A[i]]
    return

def examR():
    def list_dot(A1,A2):
        res = [[0]*len(A2) for _ in range(len(A1))]
        for i in range(len(A1)):
            for j in range(len(A2)):
                cur = 0
                for k in range(len(A1[0])):
                    cur += A1[i][k]*A2[k][j]
                res[i][j] = cur%mod
        return res
    N, K = LI()
    A = [LI() for _ in range(N)]
    now = [[1]*N]
    while(K>0):
        if K%2==1:
            now = list_dot(now,A)
        K //=2
        A = list_dot(A,A)
    ans = 0
    for i in now:
        for k in i:
            ans += k
            ans %= mod
    print(ans)
    return

def examS():
    def ketadp(a):
        n = len(a)
        dp = defaultdict(int)
        dp[0, 0, 0] = 1
        for i, less, has3 in itertools.product(range(n), (0, 1), (0, 1)):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                has3_ = has3 or d == 3
                dp[i + 1, less_, has3_] += dp[i, less, has3]

        ans = sum(dp[n, less, 1] for less in (0, 1))
        return ans
    K = SI()
    N = len(K)
    D = I()
    dp = [[0]*D for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        if i==N-1:
            for j in range(D):
                for k in range(10):
                    dp[i + 1][(j + k) % D] += dp[i][j]
    ans = dp[N][0]
    print(dp)
    print(ans)
    return

def examT():
    return

def examU():
    N = I()
    A = [LI() for _ in range(N)]
    mask = 2**N
    cst = [0]*mask
    for i in range(mask):
        cur = 0
        for j in range(N):
            for k in range(j+1,N):
                if i&(1<<j)==(1<<j) and i&(1<<k)==(1<<k):
                    cur += A[j][k]
        cst[i] = cur
    dp = [0]*mask
    for m in range(mask):
        maskT = m
        while(maskT > 0):
            cur = dp[m-maskT] + cst[maskT]
            dp[m] = max(dp[m], cur)
            maskT = (maskT - 1) & m


    ans = dp[-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examU()

"""

"""

Solution (Python):
N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]
X = [0] * (1<<N)
for s in range(1, 1<<N):
    t = s & (s-1)
    ma = sum([sum([A[i][j] for j in range(i) if 1 << j & s]) for i in range(N) if 1 << i & s])
    while t:
        ma = max(ma, X[t] + X[s^t])
        t = (t-1) & s
    X[s] = ma
print(X[-1])

Solution (Python):
N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]
X = [0] * (1<<N)
for s in range(1, 1<<N):
    t = s & (s-1)
    ma = sum([sum([A[i][j] for j in range(i) if 1 << j & s]) for i in range(N) if 1 << i & s])
    while t:
        ma = max(ma, X[t] + X[s^t])
        t = (t-1) & s
    X[s] = ma
    ss = s & (s-1)
print(X[-1])

Solution (Python):
N, = map(int, input().split())

def s(x):
    x = x & 0xFFFF0000 if x & 0xFFFF0000 else x
    x = x & 0xFF00FF00 if x & 0xFF00FF00 else x
    x = x & 0xF0F0F0F0 if x & 0xF0F0F0F0 else x
    x = x & 0xCCCCCCCC if x & 0xCCCCCCCC else x
    x = x & 0xAAAAAAAA if x & 0xAAAAAAAA else x
    return x


xs = []
for _ in range(N):
    xs.append(list(map(int, input().split())))
d = [0]*(2**N)

for i in range(1, 2**N):
    x = bin(i)[2:][::-1]
    l = len(x)-1
    d[i] = d[i-s(i)]
    
    for j, b in enumerate(x):
        if b == '1':
            d[i] += xs[l][j]

for i in range(1, 2**N):
    k = i
    while k:
        k = (k-1)&i
        nk = i^k
        d[i] = max(d[i], d[k]+d[nk])
print(d[2**N-1])

Solution (Python):
N, = map(int, input().split())

def s(x):
    x = x & 0xFFFF0000 if x & 0xFFFF0000 else x
    x = x & 0xFF00FF00 if x & 0xFF00FF00 else x
    x = x & 0xF0F0F0F0 if x & 0xF0F0F0F0 else x
    x = x & 0xCCCCCCCC if x & 0xCCCCCCCC else x
    x = x & 0xAAAAAAAA if x & 0xAAAAAAAA else x
    return x


xs = []
for _ in range(N):
    xs.append(list(map(int, input().split())))

d = [0]*(2**N)
d2 = [0]*(2**N)

for i in range(1, 2**N):
    x = bin(i)[2:][::-1]
    l = len(x)-1
    d[i] = d[i-s(i)]
    for j, b in enumerate(x):
        if b == '1':
            d[i] += xs[l][j]

for i in range(1, 2**N):
    k = i
    d2[i] = d[i]
    while k:
        k = (k-1)&i
        nk = i^k
        d2[i] = max(d2[i], d2[k]+d2[nk])
print(d2[2**N-1])

Solution (Python):

from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

ret = dfs(2**n - 1)
print(ret)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def solve(N: int, a: "List[List[int]]"):
    DP = [0]*(1 << N)
    flag = [False]*(1 << N)

    def rec(S):
        if flag[S]:
            return DP[S]
        flag[S] = True

        ans = 0
        for i in range(N):
            for j in range(i+1, N):
                if bit(S, i) and bit(S, j):
                    ans += a[i][j]
        T = (S-1) & S
        while T > 0:
            ans = max(ans, rec(T)+rec(S ^ T))
            T = (T-1) & S
        DP[S] = ans
        return ans
    print(rec((1 << N)-1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  
    solve(N, a)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [-10**30 for _ in range(1<<n)]
dp[0] = 0
for s in range(1, 1<<n):
	dp[s] = 0
	for i in range(n):
		for j in range(i+1, n):
			if (s>>i) & 1 and (s>>j) & 1:
				dp[s] += a[i][j]
	t = s
	while t > 0:
		t = (t-1)&s
		dp[s] = max(dp[s], dp[t] + dp[s^t])
print(dp[-1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

dp = [0]*(1 << n)
for bit_state in range(1 << n):
    for i in range(n):
        if not((1 << i) & bit_state): 
            tmp = 0
            for j in range(n):
                if (1 << j) & bit_state: 
                    tmp += a[i][j]
            dp[bit_state|(1<<i)] = dp[bit_state] + tmp 

dq = [0]*(1 << n)
for mask in range(1 << n):
    bit_state = mask
    while bit_state >= 0:
         bit_state &= mask
         dq[mask] = max(dq[mask], dp[bit_state] + dq[mask - bit_state])
         bit_state -= 1
print(dq[-1])

Solution (Python):

def main():
    N = int(input())
    adj = [list(map(int, input().split())) for _ in range(N)]

    dp = [0] * (2**N)
    for s in range(1, 2**N):
        tmp = 0
        for i in range(N):
            for j in range(i+1, N):
                if s>>i & 1 and s>>j & 1:
                    tmp += adj[i][j]
        t = (s-1) & s
        while t:
            tmp2 = dp[t] + dp[s^t]
            if tmp2 > tmp:
                tmp = tmp2
            t = (t - 1) & s
        dp[s] = tmp

    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n = int(input())
    m = 1 << n  
    aa = LLI(n)
    dp = [0] * m
    for s in range(3, m):
        
        value = 0
        jj = []
        for i,aai in enumerate(aa):
            if not s & 1 << i: continue
            value += sum(aai[j] for j in jj if s & 1 << j)
            jj.append(i)
        
        
        
        t = (s - 1) & s
        while t > 0:
            value_div = dp[t] + dp[s ^ t]
            if value_div > value: value = value_div
            t = (t - 1) & s
        dp[s] = value
    print(dp[m - 1])

main()

Solution (Python):
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
size = 1<<N
dp = [0]*size
cost = [0]*size
s_to_i = {1<<i:i for i in range(N)}
for s in range(size):
    for i in range(N):
        for j in range(i+1, N):
            if 1<<j & s and 1<<i & s:
                cost[s]+=a[i][j]

for s in range(1, size):
    sub = s
    while sub>=0:
        sub&=s
        dp[s] = max(dp[s^sub]+cost[sub], dp[s])
        sub-=1
print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[list(map(int,input().split())) for _ in range(n)]
    N=1<<n
    cost=[0]*N
    for mask in range(N):
        for j in range(n):
            for i in range(j):
                if((mask>>i)&1 and (mask>>j)&1):
                    cost[mask]+=A[i][j]
    dp=[-INF]*N
    dp[0]=0
    for mask in range(1,N):
        mask2=mask
        while(mask2):
            tmp=dp[mask&~mask2]+cost[mask2]
            dp[mask]=max(dp[mask],tmp)
            mask2=(mask2-1)&mask
    print(dp[-1])
resolve()

Solution (Python):

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]

same_groups=[0]*(1<<n)
for i in range(1,1<<n):
    k=i
    rb=-k&k
    ri=rb.bit_length()-1
    ar=a[ri]
    k^=rb
    val=same_groups[k]
    while k:
        pb=-k&k
        val+=ar[pb.bit_length()-1]
        k^=pb
    same_groups[i]=val

dp=[0]*(1<<n)
for grp in range(1<<n):
    g=grp
    while g:
        dp[grp]=max(dp[grp],same_groups[g]+dp[grp^g])
        g=(g-1)&grp
print(dp[-1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
a = [[int(x) for x in input().split()] for i in range(N)]
dp = [0] * (1<<N)
for S in range(1<<N):
    tmp = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if (S>>i)&1 and (S>>j)&1:
                tmp += a[i][j]
    dp[S] = max(0, tmp)
    T = (S-1)&S
    while T > 0:
        dp[S] = max(dp[S], dp[T]+dp[S^T])
        T = (T-1)&S
print(dp[(1<<N)-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

grp_score = [0] * (1<<N)
for x in range(1,1<<N):
    for i in range(N):
        bit = 1<<i
        if x & bit:
            break
    s = grp_score[x^bit] 
    s += sum(A[i][j] for j in range(i+1,N) if x & (1<<j))
    grp_score[x] = s

dp = [0] * (1<<N)
for x,s in enumerate(grp_score):
    y = x
    while y > x//2:
        z = x^y
        s = max(s, dp[y] + dp[z])
        y = (y-1) & x
    dp[x] = s

answer = dp[-1]
print(answer)

Solution (Python):
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

N = int(input())

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

dp = [0]*(2**N)

for s in range(1, 2**N):
    ppc = popcount(s)
    if ppc <= 1:
        continue
    res = sum(A[i][j] for i in range(N) for j in range(N) if 2**i&s and 2**j&s)//2
    t = s&(s-1)
    for _ in range(2**ppc - 2):
        res = max(res, dp[t] + dp[s^t])
        t = (t-1)&s
    dp[s] = res
print(dp[-1])

Solution (Python):



def iter_subset(_a): 
    _bit = _a
    yield _bit
    while 1:
        _bit = (_bit-1) & _a 
        yield _bit
        if not _bit: break



n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

total = 1<<n
gscore = [0]*total
dp = [0]*(total)

for i in range(n):
    for k in range(1<<(i)):
        gscore[k^(1<<i)] += gscore[k]
        for j,c in enumerate(A[i]):
            if (1<<j)&k:
                gscore[k^(1<<i)] += c  

        l = k
        while l:
            dp[k^(1<<i)] = max(dp[k^(1<<i)], gscore[l^(1<<i)] + dp[k^l])
            l = (l-1) & k
        dp[k^(1<<i)] = max(dp[k^(1<<i)], gscore[1<<i] + dp[k])
            


print(dp[-1])

Solution (Python):



def iter_subset(_a): 
    _bit = _a
    yield _bit
    while 1:
        _bit = (_bit-1) & _a 
        yield _bit
        if not _bit: break



n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

total = 1<<n
gscore = [0]*total
dp = [0]*(total)

for i in range(n):
    for k in range(1<<(i)):
        gscore[k^(1<<i)] += gscore[k]
        for j,c in enumerate(A[i]):
            if (1<<j)&k:
                gscore[k^(1<<i)] += c  

        for l in iter_subset(k):
            dp[k^(1<<i)] = max(dp[k^(1<<i)], gscore[l^(1<<i)] + dp[k^l])



print(dp[-1])

Solution (Python):



def iter_subset(_a): 
    _bit = _a
    yield _bit
    while 1:
        _bit = (_bit-1) & _a 
        yield _bit
        if not _bit: break



n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

total = 1<<n
gscore = [0]*total
dp = [0]*(total)

for i in range(n):
    for k in range(1<<(i)):
        gscore[k^(1<<i)] += gscore[k]
        for j,c in enumerate(A[i]):
            if (1<<j)&k:
                gscore[k^(1<<i)] += c  

        c = -(1<<50)
        for l in iter_subset(k):
            c = max(c, gscore[l^(1<<i)] + dp[k^l])
        dp[k^(1<<i)] = c
        


print(dp[-1])