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



Sample input:
3
0 10 20
10 0 -100
20 -100 0


Sample output:
20

Submission status: Accepted

Solution code:
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():
    # LCS
    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():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    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)
#    print(Order)
    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))
#    print(dp)
    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
#    print(dp)
    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
#    print(dp)
    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)
#    print(dp)
    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
#    print(dp)
    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
#        print(s,W,B)
        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
#            print(m,maskT)
#    print(dp)
    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()

"""

"""

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)
# d[i] = iに含まれるウサギが全部同じgroupに入るスコアで初期化
for i in range(1, 2**N):
    x = bin(i)[2:][::-1]
    l = len(x)-1
    d[i] = d[i-s(i)]
    # 最上位bitに対応するウサギを入れる。
    for j, b in enumerate(x):
        if b == '1':
            d[i] += xs[l][j]
# d[i] = iに含まれるウサギを分割してもいいとしてスコアの最大値. iを２つのグループk, nkに分けて足す
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))  # type: int
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#解説AC
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()

Submission status: Accepted

Solution code:
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):
        # sのうさぎたちが1グループだった場合
        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と論理積をとる」を繰り返すことで
        # すべての部分集合を列挙できる
        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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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] # i番目の人以外
    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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def iter_subset(_a): #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])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def iter_subset(_a): #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(gscore)        
#print(dp)        
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def iter_subset(_a): #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(gscore)        
#print(dp)        
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8

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()) # 1 <= N <= 16
a = [list(map(int, input().split())) for _ in range(N)]
memo = [0] * (1 << N)
flag = [0] * (1 << N)
print(f((1 << N) - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)#使った集合Sに対して,DP[S]でその総得点のmax.
#Sを部分集合として含む全てのT（次に使うグループ）へ遷移.（これがO(3^n））

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

Submission status: Accepted

Solution code:
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

    # print('b',b)
    # print('d',d)

    return d[-1]



print(main())

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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 status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 16;
const int MAXL = (1 << 16) + 10;
const ll NEG = -1e18;

vector<int> grafo[MAXL];
ll valor[MAXL],dp[MAXL],mat[MAXN][MAXN];
int vis[MAXL],N;

void brute(int pos,int bitmask,int submask){

	if(pos == N){
		if(__builtin_popcount(submask) == 0) return;
		grafo[bitmask].push_back(submask);
		return;
	}

	brute(pos+1,bitmask,submask);
	brute(pos+1, bitmask | (1 << pos), submask );
	brute(pos+1, bitmask | (1 << pos), submask | (1 << pos) );

}

void calcula(){

	for(int bitmask = 1;bitmask < (1 << N);bitmask++){
		for(int i = 0;i<N;i++){
			if(!(bitmask & (1 << i))) continue;
			for(int j = i+1;j<N;j++){
				if(!(bitmask & (1 << j))) continue;
				valor[bitmask] += mat[i][j];
			}
		}
	}

}

ll solve(int bitmask){

	if(bitmask == 0) return 0;
	if(vis[bitmask]) return dp[bitmask];

	vis[bitmask] = 1;

	ll best = NEG;

	for(int submask : grafo[bitmask]){
		best = max(best, solve(bitmask ^ submask) + valor[submask] );
	}

	return dp[bitmask] = best;

}

int main(){

	cin >> N;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			cin >> mat[i][j];
		}
	}

	brute(0,0,0);
	calcula();

	cout << solve((1 << N) - 1) << endl;

	return 0;

}