結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2018-08-24 23:58:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,240 ms / 2,000 ms |
コード長 | 476 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-06-23 11:28:56 |
合計ジャッジ時間 | 6,970 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
N = int(input()) M = [int(input()) for _ in range(N)] inf = 10 ** 6 # dp[msk]: 集合mskを買ったときの最小金額 dp = [inf] * (1 << N) dp[0] = 0 for msk in range(1 << N): for i in range(N): if msk & 1 << i: continue lp = 0 for j in range(N): if msk & 1 << j: lp += M[j] dp[msk | 1 << i] = min(dp[msk | 1 << i], dp[msk] + max(M[i] - lp % 1000, 0)) print(dp[-1])