Submission #1895049

---

Source Code Expand

(* let read_from = Scanf.Scanning.open_in "test4.txt" *)
let read_from = Scanf.Scanning.stdin

let tbl_of_line tbl h w_max =
  let rec iter n =
    if n <= w_max then let () = Scanf.bscanf read_from "%d " (fun x -> Hashtbl.add tbl (h,n) x) in iter (n + 1)
    else () in iter 1

let (--) m n =
  let rec iter i res =
    if i >= m then iter (i - 1) (i::res)
    else res in
  let rec iter' i res =
    if i <= m then iter' (i + 1) (i::res)
    else res in
  if m <= n then iter n []
  else iter' n []

let range m n =
  let rec iter i res =
  if n >= i then iter (i + 1) (i::res)
  else res in iter m []

let comb2 ls = 
  let rec iter res = function
    | x :: xs -> iter (List.fold_left (fun ls y -> (x,y) :: ls) res xs) xs
    | [] -> res in iter [] ls

let fr2 s e =                 
  let rec iter res = function
    | x :: xs -> iter (List.fold_left (fun ls y -> (x,y) :: ls) res (e--x)) xs
    | [] -> res in iter [] (e--s)

let pr x = print_endline (string_of_int x)

let pr2 x y = print_endline ((string_of_int x) ^ " " ^ (string_of_int y))

let tbl_of_stdin tbl h_max w_max =
  let rec iter n =
    if n <= h_max then
    let () = tbl_of_line tbl n w_max in iter (n+1)
    else () in iter 1

let exc_of_opt = function
  | Some x -> x
  | None -> failwith "error"

let h,w = Scanf.bscanf read_from "%d %d\n" (fun x y -> (x,y))

let garden = Hashtbl.create ((h+1) * (w+1))

let () = tbl_of_stdin garden h w

let b ij = Hashtbl.find garden ij

let calc_area h w =
  let zero_pad area =
    let rec iter j =
      if j <= w+1 then
        let () = Hashtbl.add area (0,j) 0 in 
        let () = Hashtbl.add area (h+1,j) 0 in iter (j + 1)
      else () in
    let rec iter' i =
      if i <= h+1 then
        let () = Hashtbl.add area (i,w+1) 0 in 
        let () = Hashtbl.add area (i,0) 0 in iter' (i + 1)
      else () in
    let () = iter 0 in
    let () = iter' 0 in area in
  let area = zero_pad (Hashtbl.create ((h+2) * (w+2))) in
  let lines = zero_pad (Hashtbl.create ((h+2) * (w+2))) in
  let () = List.iter (fun i -> 
               let _ = List.fold_left (fun res j ->
                           let tmp = (b (i,j)) + res in
                           let () = Hashtbl.add lines (i,j) tmp in tmp) 0 (1--w) in ())
             (1--h) in
  let () = List.iter (fun j -> 
               let _ = List.fold_left (fun res i ->
                           let tmp = (Hashtbl.find lines (i,j)) + res in
                           let () = Hashtbl.add area (i,j) tmp in tmp) 0 (1--h) in ())
             (1--w) in area

let area = calc_area h w

let area_of_rect ((i,j),(k,l)) =
  let area = Hashtbl.find area in
  (area (k,l)) + (area ((i - 1),(j - 1)))
  - (area ((i - 1),l)) - (area (k,(j - 1)))

let fixed_search f h' h w =
  List.fold_left
    (fun z' s ->
      max (List.fold_left
             (fun z e ->
               max (List.fold_left
                      (fun y j->
                        max (List.fold_left
                               (fun x len ->
                                 max (Some (f ((s,j),(e,j+len))))
                                   x) None (0--(w-j)))
                          y)
                      None (1--w))
                 z)
        None (s--h))
        z')
    None (h'--h)

let search area h w =
  let fstr = fixed_search area 1 (h - 1) w in
  match fstr with
  | Some (a,(_,(k,_))) ->
     (match fixed_search area (k+1) h w with
     | Some (b,_) -> a + b
     | None -> failwith "search")
  | None -> failwith "search"

let search_horz h w =
  let pr f = (fun x -> f x,x) in
  search (pr area_of_rect) h w

let search_vert h w = 
  let trnp ((i,j),(k,l)) = area_of_rect ((j,i),(l,k)) in
  let pr f = (fun x -> f x,x) in
  search (pr trnp) w h

let string_of_rect ((i,j),(k,l)) =
  (string_of_int i) ^ " " ^ (string_of_int j) ^ " " ^ (string_of_int k) ^ " " ^ (string_of_int l) ^ "\n"

let () = search_horz h w
       |> max (search_vert h w)
       |> pr
         (* |> (function
          *     | (Some (x,y) ,Some (z,w)) -> let () = print_string (string_of_rect y) in
          *                                   let () = pr x in
          *                                   let () = print_newline () in
          *                                   let () = print_string (string_of_rect w) in
          *                                   let () = pr z in
          *                                   let () = print_newline () in
          *                                   ()
          *     | _ -> ()) *)

Submission Info

Judge Result