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: Time Limit Exceeded

Solution code:
'''
time O(2^n * n^2 + 3^n)
'''
import sys
input=sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
pre = [0] * (1 << n)
# pre[mask] - score of group 'mask'
for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            for j in range(i + 1, n):
                if mask & (1 << j):
                    pre[mask] += a[i][j]

def rec(i, not_taken, score_so_far, mask, group):
    if i == len(not_taken):
        dp[mask] = max(dp[mask], score_so_far + pre[group])
        return
    rec(i + 1, not_taken, score_so_far, mask, group)
    rec(i + 1, not_taken, score_so_far, mask ^ (1 << not_taken[i]), group ^ (1 << not_taken[i]))

dp = [float('-inf')] * (1 << n)
# dp[mask] - best total score if we grouped rabbits from 'mask' already
dp[0] = 0
for mask in range(1 << n):
    not_taken = [i for i in range(n) if not (mask & (1 << i))]
    rec(0, not_taken, dp[mask], mask, 0)
print(dp[(1 << n) - 1])

Submission status: Time Limit Exceeded

Solution code:
'''
time O(2^n * n^2 + 3^n)
'''
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
pre = [0] * (1 << n)
# pre[mask] - score of group 'mask'
for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            for j in range(i + 1, n):
                if mask & (1 << j):
                    pre[mask] += a[i][j]

def rec(i, not_taken, score_so_far, mask, group):
    if i == len(not_taken):
        dp[mask] = max(dp[mask], score_so_far + pre[group])
        return
    rec(i + 1, not_taken, score_so_far, mask, group)
    rec(i + 1, not_taken, score_so_far, mask ^ (1 << not_taken[i]), group ^ (1 << not_taken[i]))

dp = [float('-inf')] * (1 << n)
# dp[mask] - best total score if we grouped rabbits from 'mask' already
dp[0] = 0
for mask in range(1 << n):
    not_taken = [i for i in range(n) if not (mask & (1 << i))]
    rec(0, not_taken, dp[mask], mask, 0)
print(dp[(1 << n) - 1])

Submission status: Time Limit Exceeded

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(2, m):
        # sのうさぎたちが1グループだった場合
        value = 0
        jj = []
        for i in range(n):
            if not s & 1 << i: continue
            for j in jj:
                value += aa[i][j]
            jj.append(i)
        # 部分集合tとその補集合に分かれる場合
        # 全体集合sから始めて、「1を引く」「sと論理積をとる」を繰り返すことで
        # すべての部分集合を列挙できる
        first = [True] * m
        t = (s - 1) & s
        while first[t] and t > 0:
            value_div = dp[t] + dp[s - t]
            if value_div > value: value = value_div
            first[s - t] = False
            t = (t - 1) & s
        dp[s]=value
    print(dp[m-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

popcount = lambda s: bin(s).count('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):
    b = bin(S)[::-1]
    for i in range(len(b))[::-1]:
        if b[i] == '1':
            break
    s = S&(S^(1<<i))
    T = s
    while T > 0:
        tmp = 0
        for j in range(i):
            if (T>>j)&1:
                tmp += a[i][j]
        dp[S] = max(dp[S], dp[s^T]+dp[T]+tmp)
        T = (T-1)&s
print(dp[(1<<N)-1])

Submission status: Time Limit Exceeded

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

# print(a)

dp = [-1]*((1<<n)+5)

def solve(mask):
    # print(mask)
    if (mask==(1<<n)-1):
        return 0

    if (dp[mask]!=-1):
        return dp[mask]


    notTaken = []
    for j in range(n):
        if ((mask&(1<<j))==0):
            notTaken.append(j)
    m = len(notTaken)
    ans = -1e18
    # print(str(m)+"M")

    for current in range(1, 1<<m):       
        # print(str(current)+" Current")
        # continue
        #kth bit is set in current, then notTaken[k] is selected in current group
        all = []
        newmask = mask
        for j in range(m):
            if (current&(1<<j)!=0):
                #taking j in cuurent group
                all.append(notTaken[j])
                newmask |= (1<<notTaken[j])

        p = len(all)
        score = 0
        for x in range(p):
            for y in range(x+1, p):
                score += a[all[x]][all[y]]
        ans = max(ans, score+solve(newmask))

    dp[mask] = ans
    return dp[mask]


print(solve(0))

# for mask in range(1<<n):
#     notTaken = []
#     for j in range(n):
#         if ((mask&(1<<j))==0):
#             notTaken.append(j)
#     m = len(notTaken)

#     for current in range(1<<m):
#         all = []
#         for j in range(m):
#             if (current&(1<<j)==1):
#                 #taking j in cuurent group
#                 all.append(notTaken[j])

#         p = len(all)
#         score = 0
#         for x in range(p):
#             for y in range(x+1, p):
#                 score += a[all[x]][all[y]]
#         dp[mask] = max(dp[mask], score)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

from functools import lru_cache
@lru_cache(maxsize = None)
def f(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_
    return(p)

N = int(input()) # 1 <= N <= 16
a = [list(map(int, input().split())) for _ in range(N)]
print(f(2 ** (N + 1) - 1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    # 集合sを一つのグループとしたときに得られるスコア
    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]

    # sの部分集合でs自身と空集合を除いた集合を列挙(テクニックが存在)
    t = (s-1) & s   # s自身を除く (今回は関係ないがs自身を含む場合は t = s としてあげる)
    while t > 0:
        # 集合t と, 集合sから集合tを除いた集合に分けて、それぞれ再帰的にスコアを求める
        score = max(score, f(t) + f(s ^ t))
        t = (t-1) & s

    dp[s] = score
    return dp[s]

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from itertools import combinations
from operator import or_

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)
dp = [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
# print(same_groups)

for k in range(3, n + 1):
    for grp in combinations(d, k):
        grp_i = reduce(or_, grp)
        val = float('-inf')
        for j in range(1, k + 1):
            for subgrp in combinations(grp, j):
                subgrp_i = reduce(or_, subgrp)
                comple_i = grp_i ^ subgrp_i
                val = max(val, same_groups[subgrp_i] + dp[comple_i])
        dp[grp_i] = val
        # print(k, dp, grp_i)
    # print(k)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from itertools import combinations
from operator import or_

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)
dp = [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
# print(same_groups)

for k in range(3, n + 1):
    for grp in combinations(d, k):
        grp_i = reduce(or_, grp)
        val = float('-inf')
        for j in range(1, k + 1):
            for subgrp in combinations(grp, j):
                subgrp_i = reduce(or_, subgrp)
                comple_i = grp_i ^ subgrp_i
                val = max(val, same_groups[subgrp_i] + dp[comple_i])
                # print(grp, subgrp, same_groups[subgrp_i], dp[comple_i])
        dp[grp_i] = val
        # print(k, dp, grp_i)
    # print(k)

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# U - Grouping
n = int(input())
a = [tuple(map(int,input().split())) for _ in range(n)]

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

# f(s):うさぎsをグループ分けしたときの得点の最大値。
# sのすべての部分集合tについて、f(t)+f(t|s)を計算してその最大値を求める。

def f(s):
  if memo[s] != -1:
    return memo[s]
  # now:sをグループ分けせず1グループとしたときの得点。
  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の部分集合とするが、t=sは除くため、最初はt = (s-1)&sとする。
  t = (s-1)&s
  # t = (t-1)&sとすると、sのすべての部分集合tを順に列挙できる。
  # また、tをsの部分集合としたとき、tの補集合はt xor 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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

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


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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):
        # debug("enter calcScore: S", S)
        x = S
        ret = 0
        i = 0
        while x:
            if x & 1:
                # debug(": i", i)
                for j in range(i):
                    if (S >> j) & 1:
                        # debug(": i, j, M[i,j]", i, j, M[i, j])
                        ret += M[i * N + j]
            x //= 2
            i += 1
        # debug("leave calcScore: ret", ret)
        return ret
    groupScore = [calcScore(i) for i in range(1 << N)]
    # debug(": groupScore", groupScore)

    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():
    # parse input
    N = int(input())
    M = [int(x) for x in read().split()]
    print(solve(N, M))


# tests
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
    """
# add tests above


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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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))

    # O(n^2 * 2^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]

    # O(n^3)
    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()