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:
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
#     print(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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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

Submission status: Accepted

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

# base_score[i] := i の立っている bit のウサギで一つのグループを作るときの特典
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[i] := i の立っている bit のウサギのグループが決まっているとした場合の得点の最大値
dp = [0]*(1<<N)
for i in range(1<<N):
    # i の部分集合について、ウサギのグループの分け方を全探索
    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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    # O(n^2 * 2^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[i][U] : i まで見て U <= {1, ..., n} を grouping したときの max
    # msb(U) = i ならば dp[i][U] = dp[i + 1][U] = ... = dp[n - 1][U] なので dp は使いまわせる
    # dp[i + 1][U | 1 << (i + 1)] = max((V + {i + 1} の score) + dp[i][W]) for all V + W = U
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): # 既に U = 0, ..., 2^i - 1 までは確定している
        for U in range(1 << i): # O(2^i) これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            V = U
            while V: # これだと V = 0, W = U の場合が処理されない
                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])


    # 計算量は sum_{0 <= i < n} sum_{0 <= U < 2^i} 2 ^ popcount(U)
    # = sum_{0 <= i < n} sum_{0 <= k <= i} iCk * 2^k = (3^n - 1) / 2
    print(dp[-1])
resolve()

Submission status: Accepted

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

@lru_cache(None) # 再帰にしつつ、下から計算することで再帰処理をしない
def subsets(U): # O(2^k)
    # base case
    if U == 0:
        return [0]
    # recursion
    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))

    # O(n^2 * 2^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[i][U] : i まで見て U <= {1, ..., n} を grouping したときの max
    # msb(U) = i ならば dp[i][U] = dp[i + 1][U] = ... = dp[n - 1][U] なので dp は使いまわせる
    # dp[i + 1][U | 1 << (i + 1)] = max((V + {i + 1} の score) + dp[i][W]) for all V + W = U
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): # 既に U = 0, ..., 2^i - 1 までは確定している
        for U in range(1 << i): # O(2^i) これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            for V in subsets(U): # O(2^k) where k = popcount(U)
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    # 計算量は sum_{0 <= i < n} sum_{0 <= U < 2^i} 2 ^ popcount(U)
    # = sum_{0 <= i < n} sum_{0 <= k <= i} iCk * 2^k = (3^n - 1) / 2
    print(dp[-1])
resolve()

Submission status: Accepted

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

@lru_cache(None) # 再帰にしつつ、下から計算することで再帰処理をしない
def subsets(U): # O(2^k)
    # base case
    if U == 0:
        return (0,)
    # recursion
    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))

    # O(n^2 * 2^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[i][U] : i まで見て U <= {1, ..., n} を grouping したときの max
    # msb(U) = i ならば dp[i][U] = dp[i + 1][U] = ... = dp[n - 1][U] なので dp は使いまわせる
    # dp[i + 1][U | 1 << (i + 1)] = max((V + {i + 1} の score) + dp[i][W]) for all V + W = U
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): # 既に U = 0, ..., 2^i - 1 までは確定している
        for U in range(1 << i): # O(2^i) これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            for V in subsets(U): # O(2^k) where k = popcount(U)
                W = U ^ V
                dp[U | 1 << i] = max(dp[U | 1 << i], state_to_score[V | 1 << i] + dp[W])

    # 計算量は sum_{0 <= i < n} sum_{0 <= U < 2^i} 2 ^ popcount(U)
    # = sum_{0 <= i < n} sum_{0 <= k <= i} iCk * 2^k = (3^n - 1) / 2
    print(dp[-1])
resolve()

Submission status: Accepted

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

@lru_cache(None) # 再帰にしつつ、下から計算することで再帰処理をしない
def subsets(U): # O(2^k)
    # base case
    if U == 0:
        return (0,)
    # recursion
    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))

    # O(n^2 * 2^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[i][U] : i まで見て U <= {1, ..., n} を grouping したときの max
    # msb(U) = i ならば dp[i][U] = dp[i + 1][U] = ... = dp[n - 1][U] なので dp は使いまわせる
    # dp[i + 1][U | 1 << (i + 1)] = max((V + {i + 1} の score) + dp[i][W]) for all V + W = U
    dp = [-INF] * (1 << n)
    dp[0] = 0
    for i in range(n): # 既に U = 0, ..., 2^i - 1 までは確定している
        for U in range(1 << i): # O(2^i) これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            for V in subsets(U): # O(2^k) where k = popcount(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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
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
    #状態Sの時の最大値
    #各Sから見て，全てのSの補集合Tを考える（bit1つだけ落とすのではなく，全部みる．例えば，1111から1100と0011とかもみる．）
    #Sの補集合Tで回して，dp[S]=max(dp[T]+dp[S-T])
    #Sに出てくるものが全て同じグループに入るパターンだけ別に計算する必要あり．
    
    #初期化，全部同じグループの場合を先に入れておく
    for S in range(1,MS):
        for j in range(N):
            if S>>j&1:#j番目のbitがあるなら，
                dp[S]=dp[S-(1<<j)]#j番目を加えた時の繊維を見てみる
                for k in range(N):
                    if S>>k&1:#k番目があれば
                        dp[S]+=a[j][k]
                break
            
    #メイン
    for S in range(1,MS):
        #Sの補集合，Tを列挙する
        T=S
        while T:
            T=(T-1)&S#bit演算を上手く使った補集合の列挙
            dp[S]=max(dp[S],dp[T]+dp[S-T])
            
    print(dp[MS-1])
                        
    
main()

Submission status: Accepted

Solution code:
# dp[S]=(集合Sに属するウサギのグループ分けの最高得点)=max(dp[T],dp[T\S])
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]
    # sの部分集合tだけをループ
    # for(int t=s;t>=0;t=(t-1)&s)の空集合とsを除いてfor(int t=(s-1)&s;t>0;t=(t-1)&s)
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# point[mask] : 
# maskで1が立っているbitに対応するうさぎだけで
# 1つのグループを作ったときの、そのグループの得点
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[mask] :
# maskで1が立っているbitに対応するうさぎだけで
# 最適にグループ分けしたときの得点
# maskの部分集合を_maskとすると、dpの遷移は以下
# dp[mask] = max_{_mask in mask}(dp[mask^_mask] + point[_mask])
dp = [-10**19 * 16] * (2**N)
dp[0] = 0
for mask in range(1, 2**N):
  dp[mask] = point[mask] # 一旦全員同じグループ
  _mask = (mask-1) & mask # maskの最も低い桁の1を0にしたもの
  while _mask > 0:
    dp[mask] = max(dp[mask], dp[mask^_mask] + point[_mask]) # 更新
    _mask = (_mask-1) & mask # この操作を繰り返すことでmaskの部分集合を列挙できる


print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#bit演算
# https://www.slideshare.net/KMC_JP/slide-www

# いくつかのウサギを同じグループにした時の点数を計算しておく
g = [0]*n_bit
for i in range(2,n+1):
    for j in flag_num[i]:
        #1になっている一番下の桁の取得
        left_flag = j & (-j)
        #一番左の1だけ反転
        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]

#dpを更新する
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] )

            # k==0ならbreak
            if(k==0):
                break
            #kの更新
            k = (k-1) & j
        dp[j] = temp

print(dp[n_bit - 1])

Submission status: Accepted

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

Submission status: Accepted

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