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: Wrong Answer

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


    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: Wrong Answer

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:
        j = (j-1)&i
        dp[i] = max(dp[i], dp[i-j]+base_score[j])

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

Submission status: Wrong Answer

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], score[bit - sub])
        sub = (sub - 1) & bit
        if bit == sub:
            break

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

Submission status: Wrong Answer

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]

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

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

Submission status: Wrong Answer

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], score[bit & ~sub])
        sub = (sub - 1) & bit
        if bit == sub:
            break

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

Submission status: Wrong Answer

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]
        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: Wrong Answer

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[s] + X[s^t])
        t = (t-1) & s
    X[s] = ma
print(X[-1])

Submission status: Wrong Answer

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(S)+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: Wrong Answer

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
        while T > 0:
            ans = max(ans, rec(S)+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: Time Limit Exceeded

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



def return_substrings(x):
    all_combnations = [sorted(l) for i in range(len(x)) for l in combinations(x, i+1)]
    return list(all_combnations)



def findans(arr):
    ans = 0

    for j in arr:
        for k in arr:
            ans += l[j][k]
    
    return ans
def givemask(arr):
    mask = 0
    for i in arr:
        mask += 1 << i
    return mask


d = {}
for i in return_substrings(range(n)):
    d[tuple(i)] = [findans(i), givemask(i)]

# print(d)


@lru_cache(None)
def dp(mask = 0):
    if mask == 2 ** n - 1:return 0


    currans = 0
    l1 = [j for j in range(n) if (mask >> j) & 1 == 0]
    l2 = []
    for iteration in return_substrings(l1):
        # curr = findans(iteration)
        # masknow = 0
        # for i in iteration:
        #     masknow += 1 << i
        curr, masknow = d[tuple(iteration)]

        currans = max(currans, curr + dp(mask + masknow))
    
    return currans


print(dp() // 2)

Submission status: Time Limit Exceeded

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

@functools.lru_cache(None)
def calc(S):
    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], calc(T) + calc(S^T))
        T = T - 1
        T = T & S

    return dp[S]

print(calc((1<<N)-1))

Submission status: Time Limit Exceeded

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
      for p in product([0,1],repeat=i-1):
        s = 0
        for j in range(i-1):
          if p[j]==1:
            s += 1<<com[j]
        dp[S] = max(dp[S],dp[s]+dp[S-s])
  ans = dp[-1]
  return ans
print(solve())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]

@lru_cache(maxsize=None)
def group(bit):
    res = 0
    A = bit
    while bit:
        tmp = score[bit] + group(A & ~bit)
        res = max(res, tmp)
        bit = (bit - 1) & A
    return res


print(group((1 << N)-1))

Submission status: Time Limit Exceeded

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

@lru_cache(None)
def subsets(U): # O(k * 2^k)
    bits = []
    for i in range(U.bit_length()):
        if (U >> i) & 1:
            bits.append(i)
    k = len(bits)
    res = [None] * (1 << k)
    for use in range(1 << k):
        V = 0
        for i in range(k):
            if (use >> i) & 1:
                V |= 1 << bits[i]
        res[use] = V
    return res

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

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

def subsets(U): # O(n + k * 2^k)
    bits = []
    for i in range(U.bit_length()):
        if (U >> i) & 1:
            bits.append(i)
    k = len(bits)
    res = [None] * (1 << k)
    for use in range(1 << k):
        V = 0
        for i in range(k):
            if (use >> i) & 1:
                V |= 1 << bits[i]
        res[use] = V
    return res

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): # これから 2^i, ..., 2^(i + 1) - 1 を確定させる
            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()

Submission status: Time Limit Exceeded

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


def solve(N: int, a: "List[List[int]]"):
    grp = [[] for _ in range(N)]
    gsum = [0 for _ in range(N)]
    amax = 0

    def dfs(idx):
        nonlocal amax
        if idx == N:
            s = sum(gsum)
            if amax < s:
                amax = s
                # print(f"sum={s}, grp({grp})", file=sys.stderr)
            return
        for i in range(idx + 1):
            s = sum(a[idx][j] for j in grp[i])
            gsum[i] += s
            grp[i].append(idx)
            dfs(idx + 1)
            grp[i].pop()
            gsum[i] -= s
        return

    dfs(0)
    return amax


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]]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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(j):
				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])

Submission status: Time Limit Exceeded

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
    loop = 3**N
    for i in range(loop):
        maskS = 0
        maskT = 0
        for j in range(N):
            if i%3==1:
                maskS += 2**j
            elif i%3==2:
                maskT += 2**j
            i //=3
#        print(maskS,maskT)
        cur = dp[maskS] + cst[maskT]
        dp[maskS+maskT] = max(dp[maskS+maskT],cur)
#    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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

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