結果

問題 No.286 Modulo Discount Store
ユーザー rpy3cpp
提出日時 2015-10-09 22:59:05
言語 Python3
(3.7.1 + numpy 1.14.5 + scipy 1.1.0)
結果
AC  
実行時間 433 ms
コード長 718 Byte
コンパイル時間 47 ms
使用メモリ 8,920 KB
最終ジャッジ日時 2018-12-05 20:15:44

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 18 ms
6,868 KB
case2.txt AC 21 ms
6,872 KB
case3.txt AC 111 ms
6,868 KB
case4.txt AC 19 ms
6,868 KB
case5.txt AC 20 ms
6,872 KB
case6.txt AC 19 ms
6,872 KB
case7.txt AC 212 ms
6,872 KB
case8.txt AC 19 ms
6,868 KB
case9.txt AC 18 ms
6,868 KB
case10.txt AC 17 ms
6,872 KB
case11.txt AC 60 ms
6,868 KB
case12.txt AC 19 ms
6,868 KB
case13.txt AC 19 ms
6,872 KB
case14.txt AC 109 ms
6,872 KB
case15.txt AC 19 ms
6,868 KB
case16.txt AC 19 ms
6,872 KB
case17.txt AC 20 ms
6,872 KB
case18.txt AC 433 ms
8,028 KB
case19.txt AC 62 ms
6,872 KB
case20.txt AC 19 ms
6,868 KB
case21.txt AC 29 ms
6,868 KB
case22.txt AC 19 ms
6,872 KB
case23.txt AC 19 ms
8,916 KB
case24.txt AC 107 ms
6,872 KB
case25.txt AC 18 ms
8,916 KB
case26.txt AC 38 ms
6,872 KB
case27.txt AC 19 ms
6,872 KB
case28.txt AC 37 ms
6,872 KB
case29.txt AC 210 ms
6,872 KB
case30.txt AC 20 ms
6,872 KB
case31.txt AC 19 ms
6,868 KB
case32.txt AC 23 ms
6,872 KB
case33.txt AC 22 ms
6,868 KB
case34.txt AC 20 ms
8,916 KB
case35.txt AC 19 ms
6,868 KB
case36.txt AC 21 ms
8,920 KB
case37.txt AC 19 ms
6,868 KB
case38.txt AC 39 ms
6,872 KB
case39.txt AC 19 ms
8,916 KB
case40.txt AC 213 ms
6,872 KB
sample1.txt AC 18 ms
6,868 KB
sample2.txt AC 19 ms
6,872 KB
sample3.txt AC 18 ms
8,912 KB
テストケース一括ダウンロード

ソースコード

diff #
N = int(input())
Ms = [int(input()) for i in range(N)]
dp = [float('inf')] * (1 << N)
dp[0] = 0
discount = [0] * (1 << N)
full = (1 << N) - 1
for m in range(N):
    msb = 1 << m
    for mask in range(1 << m):
        discount[msb + mask] = (discount[mask] + Ms[m]) % 1000
frontiers = [0]
for m in range(N):
    new_frontiers = []
    for f in frontiers:
        dpf = dp[f]
        dsc = discount[f]
        for idx in range(N):
            bit = 1 << idx
            if bit & f:
                continue
            nf = bit | f
            if dp[nf] == float('inf'):
                new_frontiers.append(nf)
            dp[nf] = min(dp[nf], dpf + max(0, Ms[idx] - dsc))
    frontiers = new_frontiers
print(dp[full])
0