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):


import sys
input = sys.stdin.readline

def f(s):
    if flag[s]:
        return(memo[s])
    
    p = 0
    for i in range(N):
        for j in range(i + 1, N):
            if (s >> i) & 1 and (s >> j) & 1:
                p += a[i][j]
    t = s
    while True:
        t = (t - 1) & s
        if not t:
            break
        p_ = f(t) + f(t ^ s)
        if p < p_:
            p = p_
    flag[s] = 1
    memo[s] = p
    return(p)

N = int(input()) 
a = [list(map(int, input().split())) for _ in range(N)]
memo = [0] * (1 << N)
flag = [0] * (1 << N)
print(f((1 << N) - 1))

Solution (Python):
def max_ten(s):
    if flag[s]:
        return memo[s]
    ten = 0
    
    for ai, ar in enumerate(a[:-1]):
        if (s >> ai) & 1:
            ten += sum(ar[j] for j in range(1 + ai, n) if ((s >> j) & 1))
    
    bubun = (s - 1) & s
    while bubun > 0:
        kari = max_ten(bubun) + max_ten(bubun ^ s)
        if kari > ten:
            ten = kari
        bubun = (bubun - 1) & s
    flag[s] = 1
    memo[s] = ten
    return ten


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
s = (1 << n) - 1
memo = [0] * (1 << n)
flag = [0] * (1 << n)
print(max_ten(s))

Solution (Python):
def max_ten(s):
    if memo[s]!="e":
        return memo[s]
    ten = 0
    
    for ai, ar in enumerate(a[:-1]):
        if s >> ai & 1:
            ten += sum(ar[j] * (s >> j & 1) for j in range(1 + ai, n))
    
    bubun = (s - 1) & s
    while bubun > 0:
        kari = max_ten(bubun) + max_ten(bubun ^ s)
        if kari > ten:
            ten = kari
        bubun = (bubun - 1) & s
    memo[s] = ten
    return ten


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
s = (1 << n) - 1
memo = ["e"] * (1 << n)
print(max_ten(s))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
A=[list(map(int,input().split())) for _ in range(n)]
P=[0]*(1<<n)
for s in range(1,1<<n):
    for i in range(n):
        if s&(1<<i):
            break
    p=P[s-(s&(1<<i))]
    for j in range(i+1,n):
        if s&(1<<j)!=0:
            p+=A[i][j]
    P[s]=p
DP=[0]*(1<<n)
for s in range(1<<n):
    DP[s]=P[s]
    t=s
    while t:
        DP[s]=max(DP[s],DP[t]+DP[s^t])
        t=(t-1)&s
print(DP[-1])

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

memo = [0] * (1 << n)
dp = [0] * (1 << n)

def f(s):
    if memo[s]:
        return dp[s]
    memo[s] = 1

    
    score = 0
    for i in range(n):
        for j in range(i+1, n):
            if ((s >> i) & 1) & ((s >> j) & 1):
                score += a[i][j]

    
    t = (s-1) & s   
    while t > 0:
        
        score = max(score, f(t) + f(s ^ t))
        t = (t-1) & s

    dp[s] = score
    return dp[s]

print(f((1 << n) - 1))

Solution (Python):


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

dp_sum = [0] * (1 << n)
for mask in range(3, 1 << n):
    for j in range(n):
        if mask & (1 << j):
            dp_sum[mask] = dp_sum[mask ^ (1 << j)]
            for k in range(j + 1, n):
                if mask & (1 << k):
                    dp_sum[mask] += a[j][k]
            break

dp = [0] * (1 << n)
for mask in range(3, 1 << n):
    dp[mask] = dp_sum[mask]
    sub = (mask - 1) & mask
    while sub:
        dp[mask] = max(dp[mask], dp[mask ^ sub] + dp_sum[sub])
        sub = (sub - 1) & mask
print(dp[(1 << n) - 1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

T = [0] * (1<<N)
for b in range(1<<N):
    if bin(b).count('1') <= 1: continue
    msb = len(bin(b)) - 3
    T[b] = T[b^(1<<msb)]
    for k in range(msb):
        if b&(1<<k):
            T[b] += A[k][msb]

dp = [None] * (1<<N)
def rec(b):
    if dp[b] is not None: return dp[b]
    if bin(b).count('1') <= 1: return 0
    ret = max(0,T[b])
    c = (b-1)&b
    while c > 0:
        ret = max(ret, rec(c) + rec(b^c))
        c = (c-1)&b
    dp[b] = ret
    return(ret)

print(rec(2**N-1))

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

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

POINT=[0]*(1<<N)

for i in range(1,1<<N):
    for j in range(16):
        if i & (1<<j)!=0:
            break

    ANS=POINT[i-(i & (1<<j))]

    for k in range(16):
        if i & (1<<k)!=0:
            ANS+=MAT[k][j]

    POINT[i]=ANS
        
DPLIST=[0]*((1<<N)+1)


for i in range(1<<N):
    k=i
    while k<(1<<N):
        DPLIST[k]=max(DPLIST[k],DPLIST[i]+POINT[k-i])
        k=(k+1)|i


print(DPLIST[(1<<N)-1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [LI() for _ in range(n)]
    m = 2**n

    b = [None] * m
    b[0] = 0
    ii = [2**i for i in range(n+1)]
    dd = {}
    for i in range(n):
        dd[ii[i]] = i
    c = 0
    for i in range(1,m):
        if i >= ii[c+1]:
            c += 1
        t = i - ii[c]
        k = b[t]
        d = a[c]
        while t:
            u = t ^ t - 1 & t
            t ^= u
            k += d[dd[u]]
        b[i] = k

    d = b[:]
    c = 0
    for i in range(1,m):
        if i >= ii[c+1]:
            c += 1
        k = d[i - ii[c]]
        t = i
        while t:
            u = d[t] + d[i^t]
            if k < u:
                k = u
            t = t-1 & i
        d[i] = k

    
    

    return d[-1]



print(main())

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
d = [1 << i for i 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):
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])