結果

問題 No.286 Modulo Discount Store
コンテスト
ユーザー TANIGUCHI Kousuke
提出日時 2015-11-05 10:30:52
言語 Ruby
(3.4.1)
結果
AC  
実行時間 403 ms / 2,000 ms
コード長 463 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-12-26 04:07:05
合計ジャッジ時間 6,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

n = gets.to_i
P = n.times.map { gets.to_i }
S = 1 << n
DP = Array.new(S)
SP = Array.new(S,0)
S.times do |s|
    SP[s] = n.times.inject(0) {|t,i|
        mask = 1 << i
        mask & s > 0 ? t + P[i] : t
    }

    DP[s] = n.times.select {|i|
        mask = 1 << i
        mask & s > 0
    }.map {|i|
        mask = 1 << i
        disco = SP[s ^ mask] % 1000
        up = disco > P[i] ? 0 : P[i] - disco
        DP[s ^ mask] + up
    }.min || 0
end
puts DP[S - 1]
0