結果
問題 | No.2741 Balanced Choice |
ユーザー |
|
提出日時 | 2024-04-20 19:59:02 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 2,283 ms |
コンパイル使用メモリ | 21,632 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-10-12 17:57:09 |
合計ジャッジ時間 | 4,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
Scanf.scanf "%d %d %d" (fun n w d -> let proc list = let arena = Array.make (w + 1) (-1) in arena.(0) <- 0; List.iter (fun (w0, v0) -> for i = w downto w0 do if arena.(i - w0) >= 0 then arena.(i) <- max arena.(i) (arena.(i - w0) + v0) done ) list; arena in let rec loop i list0 list1 = if i = n then proc list0, proc list1 else let t, w, v = Scanf.scanf " %d %d %d" (fun t w v -> t, w, v) in if t = 0 then loop (i + 1) ((w, v) :: list0) list1 else loop (i + 1) list0 ((w, v) :: list1) in let arena0, arena1 = loop 0 [] [] in let rec loop0 i0 mx = let rec loop1 i1 mx = if i0 + i1 > w || i1 > i0 + d then loop0 (i0 + 1) mx else let mx = if arena1.(i1) >= 0 then max mx (arena0.(i0) + arena1.(i1)) else mx in loop1 (i1 + 1) mx in if i0 > w then mx else if arena0.(i0) < 0 then loop0 (i0 + 1) mx else loop1 (max 0 (i0 - d)) mx in Printf.printf "%d\n" @@ loop0 0 0 )