(* 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 () = List.iter (fun i ->
let _ = List.fold_left (fun res j ->
let tmp = (b (i,j)) + res in
let () = Hashtbl.add area (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 area (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