結果
問題 | No.286 Modulo Discount Store |
ユーザー |
![]() |
提出日時 | 2015-10-30 19:02:05 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 176 ms / 2,000 ms |
コード長 | 595 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 7,296 KB |
実行使用メモリ | 14,080 KB |
最終ジャッジ日時 | 2024-12-26 15:15:12 |
合計ジャッジ時間 | 5,536 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
Syntax OK
ソースコード
# Here your code ! INF = 1 << 28 n = gets.to_i m = n.times.map { gets.to_i } S = 1 << n P = Array.new(S,0) dp = Array.new(S,INF) dp[0] = 0 m.each_with_index.each_with_object({0 => 0}) do |(v,i),o| mask = 1 << i o.keys.each do |s| if s & mask == 0 P[s | mask] = o[ s | mask ] = o[s] + v end end end S.times do |s| n.times do |i| mask = 1 << i if s & mask == 0 buy = m[i] - (P[s] % 1000) sum = dp[s] + (buy < 0 ? 0 : buy) dp[s | mask] = sum if sum < dp[s | mask] end end end puts dp[S-1]