Submission #1895041


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 () = 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

Submission Info

Submission Time
Task D - 庭園
User tzskp1
Language OCaml (4.02.3)
Score 0
Code Size 3984 Byte
Status WA
Exec Time 2657 ms
Memory 23808 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 50 0 / 50
Status
AC × 4
AC × 9
WA × 6
AC × 13
WA × 6
TLE × 15
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 1 ms 384 KB
sample1.txt AC 1 ms 384 KB
sample2.txt AC 1 ms 384 KB
sample3.txt AC 1 ms 512 KB
subtask0_0.txt WA 624 ms 6144 KB
subtask0_1.txt AC 843 ms 4352 KB
subtask0_10.txt AC 1137 ms 6144 KB
subtask0_11.txt WA 559 ms 5888 KB
subtask0_12.txt AC 730 ms 4480 KB
subtask0_13.txt WA 644 ms 6272 KB
subtask0_14.txt AC 622 ms 6144 KB
subtask0_2.txt AC 470 ms 3328 KB
subtask0_3.txt WA 640 ms 5504 KB
subtask0_4.txt AC 657 ms 6144 KB
subtask0_5.txt WA 739 ms 6272 KB
subtask0_6.txt AC 790 ms 6400 KB
subtask0_7.txt AC 691 ms 6272 KB
subtask0_8.txt WA 523 ms 4992 KB
subtask0_9.txt AC 732 ms 6272 KB
subtask1_0.txt TLE 2657 ms 21504 KB
subtask1_1.txt TLE 2657 ms 21760 KB
subtask1_10.txt TLE 2657 ms 19584 KB
subtask1_11.txt TLE 2657 ms 23808 KB
subtask1_12.txt TLE 2657 ms 20608 KB
subtask1_13.txt TLE 2657 ms 22144 KB
subtask1_14.txt TLE 2657 ms 20224 KB
subtask1_2.txt TLE 2657 ms 21632 KB
subtask1_3.txt TLE 2657 ms 20096 KB
subtask1_4.txt TLE 2657 ms 20736 KB
subtask1_5.txt TLE 2657 ms 21504 KB
subtask1_6.txt TLE 2657 ms 20992 KB
subtask1_7.txt TLE 2657 ms 20480 KB
subtask1_8.txt TLE 2656 ms 22420 KB
subtask1_9.txt TLE 2656 ms 21656 KB