結果

提出番号 2336
提出者 efunyo
言語 Python3
提出日時 2020-03-24 23:39:16
問題名 (70)アルゴリズムのお勉強
結果 TLE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 28ms 34624KB
2 AC 100% 29ms 35008KB
3 AC 100% 30ms 34592KB
4 AC 100% 28ms 34784KB
5 AC 100% 29ms 34912KB
6 AC 100% 35ms 35024KB
7 AC 100% 26ms 34816KB
8 AC 100% 23ms 34816KB
9 AC 100% 24ms 34800KB
10 AC 100% 24ms 34384KB
11 AC 100% 117ms 34736KB
12 AC 100% 61ms 34752KB
13 AC 100% 110ms 34624KB
14 AC 100% 65ms 34544KB
15 AC 100% 60ms 34608KB
16 AC 100% 32ms 34912KB
17 AC 100% 25ms 34800KB
18 AC 100% 24ms 35120KB
19 AC 100% 308ms 35168KB
20 AC 100% 258ms 34784KB
21 AC 100% 28ms 34752KB
22 AC 100% 806ms 35344KB
23 AC 100% 33ms 34816KB
24 TLE 0% 2048ms 36288KB
25 AC 100% 307ms 34960KB
26 AC 100% 687ms 34960KB
27 AC 100% 1672ms 35712KB
28 AC 100% 212ms 35104KB
29 TLE 0% 14696ms 39936KB
30 AC 100% 713ms 35152KB

ソースコード

#https://kotamanegi.com/Problems/view/index.php?page=70

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    t = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(N)]
    inf = 10**6

    #dp[s]:sは学習済みのアルゴリズム
    #         dp[s]はその時かかっている時間
    dp = [inf]*(1<<N)
    dp[0] = 0

    def dfs(s):
        for i in range(N):
            if (s>>i) & 1:
                continue
            hiku = 0
            for j in range(N):
                if (s>>j) & 1:
                    hiku += a[j][i]
            ns = s |1<<i
            if dp[ns]>dp[s]+t[i]-hiku:
                dp[ns] = min(dp[ns], dp[s]+t[i]-hiku)
                dfs(ns)
    dfs(0)
    print(dp[-1])

if __name__ == '__main__':
    main()