結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 29ms 35248KB
2 WA 0% 28ms 35072KB
3 WA 0% 29ms 34816KB
4 WA 0% 42ms 34880KB
5 WA 0% 28ms 34928KB
6 WA 0% 30ms 34640KB
7 WA 0% 29ms 35408KB
8 WA 0% 26ms 35008KB
9 WA 0% 26ms 34832KB
10 WA 0% 26ms 35264KB
11 WA 0% 30ms 35024KB
12 WA 0% 28ms 34976KB
13 WA 0% 29ms 35168KB
14 WA 0% 27ms 34736KB
15 WA 0% 33ms 35312KB
16 WA 0% 26ms 35248KB
17 WA 0% 26ms 35392KB
18 WA 0% 26ms 34912KB
19 WA 0% 41ms 35392KB
20 WA 0% 39ms 35200KB
21 WA 0% 31ms 34432KB
22 WA 0% 44ms 35296KB
23 WA 0% 26ms 35280KB
24 WA 0% 64ms 36288KB
25 WA 0% 34ms 35360KB
26 WA 0% 45ms 35680KB
27 WA 0% 64ms 36096KB
28 WA 0% 34ms 34880KB
29 WA 0% 198ms 40496KB
30 WA 0% 45ms 35216KB

ソースコード

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

if __name__ == '__main__':
    main()