結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
|
提出日時 | 2021-04-15 23:19:50 |
言語 | Kuin (KuinC++ v.2021.9.17) |
結果 |
AC
|
実行時間 | 317 ms / 2,000 ms |
コード長 | 1,359 bytes |
コンパイル時間 | 2,412 ms |
コンパイル使用メモリ | 145,784 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 12:31:53 |
合計ジャッジ時間 | 5,026 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
func main() var n: int :: cui@inputInt() var v: []int :: #[n]int var w: []int :: #[n]int var vSum: int :: 0 var wSum: int :: 0 for i(0, n - 1) do v[i] :: cui@inputInt() do w[i] :: cui@inputInt() do vSum :+ v[i] do wSum :+ w[i] end for var val: int :: cui@inputInt() var ansMin: int var ansMax: int block var ok: int :: 0 var ng: int :: wSum + 1 while((ok - ng).abs() > 1) var mid: int :: (ok + ng) / 2 var res: int :: f(n, v, w, mid) if(res < val) do ok :: mid else do ng :: mid end if end while do ansMin :: ok + 1 end block block var ok: int :: 0 var ng: int :: wSum + 1 while((ok - ng).abs() > 1) var mid: int :: (ok + ng) / 2 if(f(n, v, w, mid) <= val) do ok :: mid else do ng :: mid end if end while do ansMax :: ok end block do cui@print("\{ansMin}\n") do cui@print("\{vSum = val ?("inf", "\{ansMax}")}\n") func f(n: int, v: []int, w: []int, weight: int): int ; dp[i] = v ; i: 重さの和 ; v: 価値の最大値 var dp: []int :: #[weight + 1]int do dp[0] :: 1 for j(0, n - 1) for i(weight, 0, -1) if(dp[i] <> 0 & i + w[j] <= weight) do dp[i + w[j]] :: lib@max(dp[i + w[j]], dp[i] + v[j]) end if end for end for var res: int :: 0 for i(0, weight) do res :: lib@max(res, dp[i]) end for ret res - 1 end func end func