ソースコード
import heapq
import copy
from sortedcontainers import SortedSet
from sortedcontainers import SortedList
from sortedcontainers import SortedDict
import bisect
from collections import Counter
from collections import deque
import math
import itertools
from itertools import product
from itertools import groupby
import string
from functools import lru_cache
from collections import defaultdict
import sys
D = defaultdict(int)
D[()] = 0
print(D)
N = int(input())
t = list(map(int, input().split()))
a = []
for i in range(N):
a.append(list(map(int, input().split())))
preDP = [defaultdict(int) for _ in range(N)]
for i in range (1 << N):
s = set()
for j in range(N):
if (i >> j) & 1:
s.add(j)
s = frozenset(s)
for k in range(N):
base = t[k]
for elm in s:
base = max(0,base-a[elm][k])
preDP[k][s] = base
dp = [defaultdict(lambda : 10**15) for _ in range(N+1)]
dp[0][frozenset()] = 0
for i in range(N):
for key,value in dp[i].items():
for nx in range(N):
if nx in key:
continue
next = set(key)
next.add(nx)
dp[i+1][frozenset(next)] = min(dp[i+1][frozenset(next)],value+preDP[nx][key])
print(min(dp[-1].values()))