結果
問題 | No.2741 Balanced Choice |
ユーザー | xsd |
提出日時 | 2024-04-20 19:59:02 |
言語 | OCaml (5.1.0) |
結果 |
AC
|
実行時間 | 309 ms / 2,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 1,804 ms |
コンパイル使用メモリ | 21,760 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-20 19:59:06 |
合計ジャッジ時間 | 3,814 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 186 ms
6,816 KB |
testcase_01 | AC | 244 ms
6,944 KB |
testcase_02 | AC | 269 ms
6,944 KB |
testcase_03 | AC | 309 ms
6,940 KB |
testcase_04 | AC | 308 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 72 ms
6,944 KB |
testcase_08 | AC | 125 ms
6,940 KB |
testcase_09 | AC | 63 ms
6,940 KB |
testcase_10 | AC | 82 ms
6,940 KB |
testcase_11 | AC | 128 ms
6,940 KB |
ソースコード
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 )