Submission #1453245

---

Source Code Expand

let memoize n f =
  let dp = Hashtbl.create n in
  let rec get x =
    try Hashtbl.find dp x with
    | Not_found ->
        let result = f get x in
        Hashtbl.add dp x result;
        result in
  get

let () =
  let a, b = Scanf.scanf "%d %d\n" (fun a b -> a, b) in
  let as_ = Array.init a (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  let bs = Array.init b (fun _ -> Scanf.scanf "%d " (fun b -> b)) in
  let solve = memoize (a * b) (fun solve (i, j) ->
    match i < a, j < b with
    | false, false -> (0, 0)
    | true, false ->
        let (enemy, me) = solve (i + 1, j) in
        (as_.(i) + me, enemy)
    | false, true ->
        let (enemy', me') = solve (i, j + 1) in
        (bs.(j) + me', enemy')
    | true, true ->
        let (enemy, me) = solve (i + 1, j) in
        let (enemy', me') = solve (i, j + 1) in
        if as_.(i) + me <= bs.(j) + me' then (bs.(j) + me', enemy')
        else (as_.(i) + me, enemy)) in
  Printf.printf "%d\n" @@ fst @@ solve (0, 0)

Submission Info

Judge Result