Submission #2542277


Source Code Expand

module MultiSet = struct
  module type S = sig
    type elt
    type t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val count : elt -> t -> int
    val add : elt -> t -> t
    val remove : elt -> t -> t
    val clear : elt -> t -> t
    val cardinal : t -> int
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val max_elt : t -> elt
    val subset : t -> t -> bool
    val inter : t -> t -> t
  end

  module Make (E : Set.OrderedType) : S with type elt = E.t = struct
    module EltMap = Map.Make (E)
    type elt = EltMap.key
    type t = int EltMap.t

    let empty = EltMap.empty
    let is_empty = EltMap.is_empty
    let mem = EltMap.mem
    let count x m = try EltMap.find x m with Not_found -> 0
    let add x m = EltMap.add x (count x m + 1) m
    let remove x m =
      match EltMap.find x m with
      | 1 -> EltMap.remove x m
      | n -> EltMap.add x (n - 1) m
      | exception Not_found -> m
    let clear = EltMap.remove
    let cardinal m = EltMap.fold (fun _ -> ( + )) m 0
    let fold f = EltMap.fold (fun x n -> Array.fold_right f (Array.make n x))
    let max_elt m = fst (EltMap.max_binding m)
    let min_elt m = fst (EltMap.min_binding m)
    let subset m1 m2 = EltMap.for_all (fun x n1 -> n1 <= count x m2) m1
    let inter m1 m2 = EltMap.merge (fun _ o1 o2 ->
      match o1, o2 with
      | None, _ | _, None -> None
      | Some n, Some m -> Some (min n m)) m1 m2
  end
end

module IntMultiSet = MultiSet.Make (struct
  type t = int
  let compare = compare 
end)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  Array.fold_left (fun (count, s) a ->
    begin
      count + IntMultiSet.count 0 s,
      IntMultiSet.add a
        (IntMultiSet.fold (fun a' ->
          IntMultiSet.add (a + a')) s IntMultiSet.empty)
    end) (0, IntMultiSet.empty) as_
  |> (fun (count, s) ->
      count + IntMultiSet.count 0 s)
  |> Printf.printf "%d\n"

Submission Info

Submission Time
Task A - Zero-Sum Ranges
User fetburner
Language OCaml (4.02.3)
Score 0
Code Size 2034 Byte
Status TLE
Exec Time 2104 ms
Memory 8448 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 200
Status
AC × 3
AC × 8
TLE × 13
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 384 KB
sample_02.txt AC 3 ms 512 KB
sample_03.txt AC 1 ms 384 KB
subtask_1_01.txt AC 1 ms 384 KB
subtask_1_02.txt AC 1 ms 384 KB
subtask_1_03.txt TLE 2104 ms 7296 KB
subtask_1_04.txt TLE 2103 ms 3712 KB
subtask_1_05.txt TLE 2104 ms 7168 KB
subtask_1_06.txt TLE 2103 ms 6528 KB
subtask_1_07.txt TLE 2104 ms 6528 KB
subtask_1_08.txt TLE 2104 ms 6528 KB
subtask_1_09.txt TLE 2104 ms 6400 KB
subtask_1_10.txt TLE 2103 ms 8448 KB
subtask_1_11.txt TLE 2104 ms 6528 KB
subtask_1_12.txt TLE 2104 ms 6528 KB
subtask_1_13.txt TLE 2104 ms 6400 KB
subtask_1_14.txt TLE 2103 ms 6528 KB
subtask_1_15.txt TLE 2104 ms 6400 KB