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 |
|
|
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 |