結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2017-08-09 10:48:02 |
言語 | Ruby (3.4.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 525 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-10-12 03:50:25 |
合計ジャッジ時間 | 48,334 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 TLE * 6 |
コンパイルメッセージ
Syntax OK
ソースコード
N = gets.to_i V, W = [], [] N.times do |i| v, w = gets.split.map &:to_i V << v W << w end VALUE = gets.to_i dp = [-1.to_i] * (1e5.to_i + 1) dp[0] = 0 N.times do |i| 1e5.to_i.downto(0) do |j| next if dp[i][j] == -1 dp[j + W[i]] = [dp[j + W[i]], dp[j] + V[i]].max if j + W[i] <= 1e5.to_i end end _ = 0 (1e5 + 1).to_i.times do |i| _ = [_, dp[i]].max dp[i] = [dp[i], _].max end puts [dp.find_index(VALUE), 1].max puts VALUE == V.inject(:+) ? "inf" : dp[0..1e5.to_i].take_while { |x| x <= VALUE }.size - 1