結果

問題 No.286 Modulo Discount Store
ユーザー Tawara
提出日時 2015-10-14 01:25:53
言語 Python2
(2.7.18)
結果
AC  
実行時間 522 ms / 2,000 ms
コード長 417 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 12,096 KB
最終ジャッジ日時 2024-07-21 07:39:07
合計ジャッジ時間 3,319 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = input()
M = [input() for i in xrange(N)]
ALL = 2**N - 1
dp = [150001]*(ALL+1)
total = {1<<i:M[i] for i in xrange(N)}
for i in xrange(N):
	dp[1<<i] = M[i]
for i in xrange(1,N):
	for j in xrange(ALL):
		if bin(j).count("1") == i:
			for k in xrange(N):
				bit = 1<<k
				if (j & bit) == 0:
					nxt = j|bit
					total[nxt] = total[j] + M[k]
					dp[nxt] = min(dp[nxt],dp[j]+max(0,M[k]-total[j]%1000))
print dp[ALL]
0