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):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n = val()
l = []

for i in range(n):
    l.append(li())


ans = [-float('inf') for i in range(2 ** n)]

ans[0] = 0

for i in range(1, 2 ** n):


    curr = 0
    for j in range(n):
        for k in range(n):
            if (i >> j) & 1 == (i >> k) & 1 == 1:curr += l[j][k]
    
    curr //= 2

    ind = i & (i - 1)

    while ind:
        curr = max(curr, ans[ind] + ans[ind ^ i])
        ind = (ind - 1) & i
    
    ans[i] = curr

print(max(ans))

Solution (Python):

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

memo = [-1 for _ in range(2**n)]




def f(s):
  if memo[s] != -1:
    return memo[s]
  
  now = 0
  for i in range(n-1):
    for j in range(i+1,n):
      if (s>>i)&1 == 1 and (s>>j)&1 == 1:
        now += a[i][j]
  ret = now
  
  t = (s-1)&s
  
  
  while(t > 0):
    ret = max(ret,f(t)+f(t^s))
    t = (t-1)&s
  memo[s] = ret
  return ret

print(f(2**n-1))

Solution (Python):
def f(m):
    if z[m]==-1:
        z[m]=q[m]
        s=(m-1)&m
        while s:
            z[m]=max(z[m],f(s)+q[s^m])
            s=(s-1)&m
    return z[m]
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
t=1<<n
q=[0]*t
for m in xrange(t):
    s=0
    for i in xrange(n):
        if (m>>i)&1:
            for j in xrange(i):
                if (m>>j)&1:
                    q[m]+=a[i][j]
z=[-1]*t
print f(t-1)

Solution (Python):
def f(m):
    if z[m]==-1:
        z[m]=q[m]
        s=(m-1)&m
        while s:
            z[m]=max(z[m],f(s)+f(s^m))
            s=(s-1)&m
    return z[m]
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
t=1<<n
q=[0]*t
for m in xrange(t):
    s=0
    for i in xrange(n):
        if (m>>i)&1:
            for j in xrange(i):
                if (m>>j)&1:
                    q[m]+=a[i][j]
z=[-1]*t
print f(t-1)

Solution (Python):
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
t=1<<n
q=[0]*t
for m in xrange(t):
    s=0
    for i in xrange(n):
        if (m>>i)&1:
            for j in xrange(i):
                if (m>>j)&1:
                    q[m]+=a[i][j]
z=[-(1<<64)]*t
for m in xrange(t):
    z[m]=q[m]
    s=m
    while s:
        z[m]=max(z[m],z[s]+q[s^m])
        s=(s-1)&m
print z[-1]

Solution (Python):
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
t=1<<n
q=[-(1<<64)]*t
for m in xrange(t):
    s=0
    for i in xrange(n):
        if (m>>i)&1:
            for j in xrange(i):
                if (m>>j)&1:
                    s+=a[i][j]
    q[m]=max(q[m],s)
z=[-(1<<64)]*t
for m in xrange(t):
    z[m]=q[m]
    s=m
    while s:
        z[m]=max(z[m],z[s]+q[(~s)&m])
        s=(s-1)&m
print z[-1]

Solution (Python):
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
t=1<<n
q=[-(1<<64)]*t
for m in xrange(t):
    s=0
    for i in xrange(n):
        if (m>>i)&1:
            for j in xrange(i):
                if (m>>j)&1:
                    s+=a[i][j]
    q[m]=max(q[m],s)
z=[-(1<<64)]*t
for m in xrange(t):
    z[m]=q[m]
    s=m
    while s:
        z[m]=max(z[m],z[s]+q[(s^m)&m])
        s=(s-1)&m
print z[-1]

Solution (Python):
def nasu(x):
  L = []
  cnt = 0
  while x:
    if x & 1:
      L.append(cnt)
    x >>= 1
    cnt += 1
  ans = 0
  for i in range(len(L) - 1):
    for j in range(i + 1, len(L)):
      ans += a[L[i]][L[j]]
  return ans

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
DP = [0] * (1 << N)
for m in range(1, N + 1):
  x = (1 << m) - 1
  while x < (1 << N):
    DP[x] = nasu(x)
    b = x
    while b:
      d = x ^ b
      DP[x] = max(DP[x], DP[d] + DP[b])
      b = (b - 1) & x

    y = x & -x;
    z = x + y
    x = (((x & ~ z) // y) >> 1) | z

print(DP[-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
data = ILL(N)

dp = [0 for b in range(1<<N)]

for b in range(1<<N):
  member = []
  for i in range(N):
    if (b>>i)&1:
      for j in member:
        dp[b] += data[i][j]
      member.append(i)

for b in range(1<<N):
  k = b
  while True:
    k -= 1
    k &= b
    dp[b] = max(dp[b],dp[k]+dp[b-k])
    if not k: break
    
print(dp[-1])

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    S = (1 << i) - 1
    while S < (1 << N):
      for k in range(N):
        if S>>k & 1:
          break
      dp[S] = dp[S-(1<<k)]
      for j in range(k+1,N):
        if S>>j & 1:
          dp[S] += A[k][j]
      x = S & -S; y = S + x
      S = ((S & ~y) // x >> 1) | y
  for i in range(2,N+1):
    S = (1 << i) - 1
    while S < (1 << N):
      T = (S-1)&S
      while T>0:
        dp[S] = max(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
      x = S & -S; y = S + x
      S = ((S & ~y) // x >> 1) | y
  ans = dp[-1]
  return ans
print(solve())

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

def bit(S, j):
    
    return (S>>j)&1

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

dp = [-INF for i in range(1<<N)]
dp[0] = 0

for S in range(1<<N):
    dp[S] = 0
    for i in range(N):
        for j in range(i+1, N):
            if bit(S,i) and bit(S,j): dp[S] += a[i][j]

    T = S - 1
    T = T & S
    while T > 0:
        dp[S] = max(dp[S], dp[T] + dp[S^T])
        T = T - 1
        T = T & S

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

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = 0
      for c in com:
        S += 1<<c
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com:
        dp[S] += A[last][c]
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = 0
      for c in com:
        S += 1<<c
      T = (S-1)&S
      while T>0:
        dp[S] = max(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
  ans = dp[-1]
  return ans
print(solve())

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  dp = [0]*(1<<N)
  dp[0] = 0
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      last = com[-1]
      dp[S] = dp[S-(1<<last)]
      for c in com:
        dp[S] += A[last][c]
  for i in range(2,N+1):
    for com in combinations(range(N),i):
      S = sum([1<<c for c in com])
      T = (S-1)&S
      while T>0:
        dp[S] = max(dp[S],dp[T]+dp[S-T])
        T = (T-1)&S
  ans = dp[-1]
  return ans
print(solve())

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:, :], ), cache=True)
def main(A):
    N = A.shape[0]
    INF = 1 << 60
    dp = np.full(1 << N, -INF, np.int64)
    dp[0] = 0
    for s in range(1 << N):
        x = 0
        for j in range(N):
            for i in range(j):
                if (s & (1 << j)) and (s & (1 << i)):
                    x += A[i, j]
        t = s
        while t:
            x = max(x, dp[t] + dp[s ^ t])
            t = (t - 1) & s
        dp[s] = x
    return dp[-1]

N = int(readline())
A = np.array(read().split(), np.int64).reshape(N, N)

print(main(A))

Solution (Python):

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

    
    cost = [0] * (1 << N)
    for bit in range(1 << N):
        for i in range(N):
            for j in range(i + 1, N):
                if bit >> i & 1 and bit >> j & 1:
                    cost[bit] += AB[i][j]

    dp = [0] * (1 << N)
    for s in range(1, 1 << N):
        t = s
        while t > 0:
            dp[s] = max(dp[s], dp[s - t] + cost[t])
            t = s & (t - 1)
            
    print(dp[-1])


if __name__ == "__main__":
    resolve()

Solution (Python):




import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, M):
    FULLBIT = (1 << N) - 1

    def calcScore(S):
        
        x = S
        ret = 0
        i = 0
        while x:
            if x & 1:
                
                for j in range(i):
                    if (S >> j) & 1:
                        
                        ret += M[i * N + j]
            x //= 2
            i += 1
        
        return ret
    groupScore = [calcScore(i) for i in range(1 << N)]
    

    table = [None] * (1 << N)

    def sub(S):
        ret = table[S]
        if ret != None:
            return ret
        ret = groupScore[S]
        x = (S - 1) & S
        while x > 0:
            y = (~x) & S
            v = sub(x) + sub(y)
            if v > ret:
                ret = v
            x = (x - 1) & S
        table[S] = ret
        return ret

    return sub(FULLBIT)


def main():
    
    N = int(input())
    M = [int(x) for x in read().split()]
    print(solve(N, M))



T1 = """
3
0 10 20
10 0 -100
20 -100 0
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    20
    """


T2 = """
2
0 -10
-10 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    0
    """


T3 = """
4
0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000
1000000000 1000000000 0 -1
1000000000 1000000000 -1 0
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4999999999
    """


T4 = """
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
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    132
    """



def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
def main() -> None:
    N = int(input())
    a = [[0]*N for _ in range(N)]
    for i in range(N):
        *a[i], = map(int, input().split())

    sums = [0]*(1<<N)
    for s in range(1, 1<<N):
        for i in range(1, N):
            for j in range(i):
                if (s>>i & 1) & (s>>j & 1):
                    sums[s] += a[i][j]

    dp = [0]*(1<<N)
    for s in range(1, 1<<N):
        t = s
        while t > 0:
            dp[s] = max(dp[s], dp[s & ~t] + sums[t])
            t = s & (t-1)

    print(dp[-1])
 
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = [[0]*N for _ in range(N)]
for i in range(N):
    *a[i], = map(int, input().split())

sums = [0]*(1<<N)
for s in range(1, 1<<N):
    for i in range(1, N):
        for j in range(i):
            if (s>>i & 1) & (s>>j & 1):
                sums[s] += a[i][j]

dp = [0]*(1<<N)
for s in range(1, 1<<N):
    t = s
    while t > 0:
        dp[s] = max(dp[s], dp[s & ~t] + sums[t])
        t = s & (t-1)

print(dp[-1])

Solution (Python):
def main() -> None:
    N = int(input())
    A = [[int(x) for x in input().split()] for _ in range(N)]

    dp = [0] * (1 << N)
    dp[0] = 1
    for state in range(1 << N):
        for i in range(N):
            for j in range(i, N):
                if (state >> i & 1) and (state >> j & 1):
                    dp[state] += A[i][j]
        sub_state = state & (state - 1)
        while sub_state > 0:
            not_sub = state & ~sub_state
            if sub_state < not_sub:
                break
            dp[state] = max(dp[state], dp[sub_state] + dp[not_sub])
            sub_state = state & (sub_state - 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    
    state_to_score = [0] * (1 <<  n)
    for U in range(1 << n):
        for i in range(n):
            if not U >> i & 1:
                continue
            for j in range(i):
                if U >> j & 1:
                    state_to_score[U] += A[i][j]

    
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for U in range(1, 1 << n):
        V = U
        while V:
            W = U ^ V
            dp[U] = max(dp[U], dp[W] + state_to_score[V])
            V = (V - 1) & U

    print(dp[-1])
resolve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [None]*pow(2,n)
val = [None]*pow(2,n)
for b in range(pow(2,n)):
    v = 0
    for i in range(n):
        for j in range(i,n):
            if b&1<<i and b&1<<j:
                v += a[i][j]
    val[b] = v
            
def sub(b):
    if dp[b] is not None:
        return dp[b]
    ans = 0
    sb = b

    while True:
        sb = (sb-1) & b
        if sb==b:
            break
        ans = max(sub(sb) + val[b-sb], ans)
    dp[b] = ans
    return ans
    
print(sub(pow(2,n)-1))

Solution (Python):
N, *A = map(int, open(0).read().split())
A = list(zip(*[iter(A)] * N))

M = 2 ** N

S = [0] * M
for state in range(M):
    for i, ai in enumerate(A):
        for j in range(i + 1, N):
            if (state >> i) & 1 and (state >> j) & 1:
                S[state] += ai[j]

dp = [0] * M
for state in range(M):
    mask = state
    while mask:
        dp[state] = max(
            dp[state],
            dp[state - mask] + S[mask]
        )
        mask = (mask - 1) & state

print(dp[-1])

Solution (Python):
def solve():
    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    scores = [0] * (1<<N)
    for S in range(1, 1<<N):
        for i in range(N):
            if (S>>i) & 1:
                score = scores[S ^ (1<<i)]
                for j in range(i+1, N):
                    if (S>>j) & 1:
                        score += Ass[i][j]
                scores[S] = score
                break

    def enumSubset(S):
        subSs = []
        subS = S
        while True:
            subSs.append(subS)
            subS = (subS-1) & S
            if subS == S:
                break
        subSs.reverse()
        return subSs

    dp = [0] * (1<<N)
    for S in range(1<<N):
        subSs = enumSubset(S)
        dp[S] = max([scores[subS] + dp[S-subS] for subS in subSs])

    print(dp[-1])


solve()

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = []
    for i in range(N):
        A.append(read_ints())
    base = [0]*(2**N)
    for i in range(2**N):
        for j in range(N):
            for k in range(j):
                if i & (1<<j) and i & (1<<k):
                    base[i] += A[j][k]
    dp = [0]*(2**N)
    for i in range(2**N):
        j = i
        while j > 0:
            dp[i] = max(dp[i], dp[i-j]+base[j])
            j = (j-1)&i
    return dp[2**N-1]


if __name__ == '__main__':
    print(solve())

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


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


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

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

Solution (Python):
import itertools


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    score_list = [0 for _ in range(1 << N)]
    for S in range(1, 1 << N):
        group = [r for r in range(N) if (S >> r) & 1 == 1]
        score_list[S] = sum([A[i][j] for i, j in itertools.combinations(group, 2)])
    dp = [0 for _ in range(1 << N)]
    for S in range(1, 1 << N):
        score = score_list[S]
        T = (S - 1) & S
        while T > 0:
            x = dp[S ^ T] + dp[T]
            score = max(score, x)
            T = (T - 1) & S
        dp[S] = score
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()

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

data=[0]*2**N
for i in range(1,2**N):
    res=0
    m=[j for j in range(N) if i>>j&1==1]
    for j in m:
        for k in m:
            res+=a[j][k]
    res//=2
    data[i]=res

dp=[0]*2**N
for i in range(1,2**N):
    res=data[i]
    j=(i-1)&i
    while j>0:
        temp=dp[j]+dp[i-j]
        res=max(res,temp)
        j=(j-1)&i
    dp[i]=res

print(dp[-1])

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


N = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(N))

score = [0] * (1 << N)
for bit in range(1 << N):
    for i in range(N-1):
        if (bit >> i) & 1:
            for j in range(i + 1, N):
                if (bit >> j) & 1:
                    score[bit] += A[i][j]


dp = [0] * (1 << N)
for bit in range(1 << N):
    sub = bit
    while True:
        dp[bit] = max(dp[bit], dp[sub] + score[bit & ~sub])
        sub = (sub - 1) & bit
        if bit == sub:
            break

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

Solution (Python):
n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
gr = [0]
for i in range(n):
    for j, s in enumerate(gr[:]):
        for k in range(n):
            if (j >> k) & 1 == 1:
                s += a[i][k]
        gr.append(s)

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

Solution (Python):
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
score = [0]*(1<<N)

for S in range(1<<N):
    for i in range(N):
        if (S>>i)&1:
            for j in range(i+1, N):
                if (S>>j)&1:
                    score[S] += a[i][j]
    
dp = [-10**18]*(1<<N)
dp[0] = 0

for S in range(1<<N):
    T = S
    
    while True:
        dp[S] = max(dp[S], dp[T]+score[S-T])
        T = (T-1)&S

        if T==S:
            break

print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    
    state_to_score = [0] * (1 << n)
    for U in range(1 << n):
        for i in range(n):
            if (U >> i) & 1 == 0:
                continue
            for j in range(i):
                if (U >> j) & 1:
                    state_to_score[U] += A[i][j]

    
    
    
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): 
        for U in range(1 << i): 
            V = U
            while V: 
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])
                V = (V - 1) & U
            
            dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[1 << i] + dp[U])


    
    
    print(dp[-1])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache

@lru_cache(None) 
def subsets(U): 
    
    if U == 0:
        return [0]
    
    d = U.bit_length() - 1
    U ^= 1 << d
    prev = subsets(U)
    return prev + [U | 1 << d for U in prev]

def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    
    state_to_score = [0] * (1 << n)
    for U in range(1 << n):
        for i in range(n):
            if (U >> i) & 1 == 0:
                continue
            for j in range(i):
                if (U >> j) & 1:
                    state_to_score[U] += A[i][j]

    
    
    
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): 
        for U in range(1 << i): 
            for V in subsets(U): 
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    
    
    print(dp[-1])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
from itertools import chain

@lru_cache(None) 
def subsets(U): 
    
    if U == 0:
        return (0,)
    
    d = U.bit_length() - 1
    U ^= 1 << d
    prev = subsets(U)
    return tuple(chain(prev, (U | 1 << d for U in prev)))

def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    
    state_to_score = [0] * (1 << n)
    for U in range(1 << n):
        for i in range(n):
            if (U >> i) & 1 == 0:
                continue
            for j in range(i):
                if (U >> j) & 1:
                    state_to_score[U] += A[i][j]

    
    
    
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): 
        for U in range(1 << i): 
            for V in subsets(U): 
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    
    
    print(dp[-1])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
from itertools import chain

@lru_cache(None) 
def subsets(U): 
    
    if U == 0:
        return (0,)
    
    d = U.bit_length() - 1
    U ^= 1 << d
    prev = subsets(U)
    return tuple(chain(prev, [U | 1 << d for U in prev]))


def resolve():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))

    
    state_to_score = [0] * (1 << n)
    for U in range(1 << n):
        for i in range(n):
            if (U >> i) & 1 == 0:
                continue
            for j in range(i):
                if (U >> j) & 1:
                    state_to_score[U] += A[i][j]

    
    
    
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): 
        for U in range(1 << i): 
            for V in subsets(U): 
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    print(dp[-1])
resolve()

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


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


dp = [0]*(1 << n)
flag = [False]*(1 << n)


def dfs(s):
    if flag[s] or bin(s).count("1") <= 1:
        return dp[s]
    flag[s] = True
    tmp = 0
    for i in range(n):
        for j in range(i+1, n):
            if bit(s, i) & bit(s, j):
                tmp += a[i][j]
    score = tmp
    t = (s-1) & s
    while 0 < t:
        score = max(score, dfs(t)+dfs(s ^ t))
        t = (t-1) & s
    dp[s] = score
    return dp[s]


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

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