結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー Tawara
提出日時 2015-10-14 01:25:53
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 417 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 271 ms
コンパイル使用メモリ 77,460 KB
最終ジャッジ日時 2025-12-03 17:28:27
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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