結果

提出番号 2290
提出者 ne0n
言語 Python3
提出日時 2019-12-07 22:45:06
問題名 (70)アルゴリズムのお勉強
結果 TLE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 45ms 32592KB
2 AC 100% 26ms 33104KB
3 AC 100% 45ms 33232KB
4 AC 100% 24ms 32640KB
5 AC 100% 28ms 33088KB
6 AC 100% 1571ms 32720KB
7 AC 100% 46ms 33008KB
8 AC 100% 24ms 33248KB
9 AC 100% 25ms 32720KB
10 AC 100% 44ms 32976KB
11 TLE 0% 20002ms 0KB
12 TLE 0% 15744ms 33088KB
13 TLE 0% 20003ms 0KB
14 TLE 0% 15848ms 33088KB
15 TLE 0% 15574ms 32976KB
16 AC 100% 200ms 33184KB
17 AC 100% 45ms 33008KB
18 AC 100% 42ms 32800KB
19 TLE 0% 20003ms 0KB
20 TLE 0% 20002ms 0KB
21 AC 100% 197ms 32592KB
22 TLE 0% 20002ms 0KB
23 AC 100% 1578ms 32768KB
24 TLE 0% 20002ms 0KB
25 TLE 0% 20002ms 0KB
26 TLE 0% 20002ms 0KB
27 TLE 0% 20002ms 0KB
28 TLE 0% 20002ms 0KB
29 TLE 0% 20002ms 0KB
30 TLE 0% 20002ms 0KB

ソースコード

n = int(input())
t = list(map(int,input().split()))
a = list()
dp = [10000 for i in range(2**n)]
for i in range(n):
    a.append(list(map(int,input().split())))
oo = "0"*n
#for i in range(n):
#    omae = oo[:i] + "1" + oo[i+1:]
#    omae_int = 0
#    for j in range(n):
#        omae_int += 2**j*int(omae[-1*(j+1)])
#    dp[omae_int] = 0
dp[0] = 0
def func(name):
    for i in range(n):
        if name == "1"*n:
            break
        if name[i] == "1":
            continue
        add = 0
        for j in range(n):
            if name[j] == "1":
                add += a[-1*(j+1)][-1*(i+1)]
        after = name
        after = after[:i] +"1"+after[i+1:]
        after_int = 0
        name_int = 0
        for j in range(n):
            after_int += (2**j)*int(after[-1*(j+1)])
            name_int += (2**j)*int(name[-1*(j+1)])
        
        if t[i]-add > 0:
            dp[after_int] = min(dp[after_int],dp[name_int] + t[i] - add)
        else:
            dp[after_int] = min(dp[after_int],dp[name_int])
        func(after)
omae = "0"*n
func(omae)
print(dp[2**n-1])