結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2021-06-10 12:25:01 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 236 ms / 2,000 ms |
コード長 | 422 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-11-29 19:47:59 |
合計ジャッジ時間 | 5,974 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
Syntax OK
ソースコード
N = gets.to_i M = N.times.map { gets.to_i } L = 1 << N dp = Array.new(L, Float::INFINITY) dp[0] = 0 L.times do |mask| cur_v = 0 M.each_with_index do |m, i| next if mask[i] == 0 cur_v += m end M.each_with_index do |m, i| next if mask[i] == 1 v = m - cur_v % 1000 v = 0 if v < 0 nv = dp[mask] + v nmask = mask | (1 << i) dp[nmask] = nv if dp[nmask] > nv end end puts dp[L - 1]