(* Solution to ACM ICPC 2011 problem F: works.
* http://cm.baylor.edu/digital/icpc2011.pdf
* Danny Sleator *)
(* There's a simple dynamic programming solution. You insert the
* machines from lowest day to highest day. When you insert a new
* machine you figure out the maximum amount of money you could have when
* you inserted it. The way you do this is to consider all the prior
* machines, and for each one you see how much it would have earned at
* the current time. You take the option that maximizes this and insert
* the new machine.
*
* The problem with this solution is that it's O(n^2). To make this
* more efficient, you maintain a list of the machines (in order of
* increasing slope) that can possibly be optimum at some point in the
* future. This is like maintaining the lower hull of a set of
* lines. I call this the "curve" in the comments below.
*
* The two operations we need to do on this data structure are (1)
* lookup the value of this lower hull curve at a particular point
* (before we insert a new machine), and (2) when we insert the
* machine, this new line needs to be inserted into the lower hull.
*
* The data structure is a list of lines, ordered by slope, that form
* the lower hull. We store them in a binary search tree (Ocaml set).
* Operation (1) can be done by trying lines in order from left to
* right, until the y value decreases. At this point we've gone too
* far. Each line that we try that is not as good as the next one can
* be deleted from the data structure. So the total time for (1) is
* O(n log n).
*
* Operation (2) is done by splitting the list at the slope of the new
* line to be inserted. And then the new line may dominate a bunch of
* lines on either side of of its slope. So we split, and traverse
* these two lists deleting as long as necessary, then we join the two
* lists together, with the new one in the middle. Again, the total
* cost of this is O(n log n) *)
module Lset = Set.Make (struct type t = int*int*int let compare = compare end)
open Lset
(* evaluate the given line at the given point *)
let eval (sl,x0,y0) x = (x-x0)*sl + y0
(* Given two non-parallel lines, compute the x coorinate of their
* intersection (in floating point) *)
let xint (s1,x1,y1) (s3,x3,y3) =
(float_of_int (s1*x1 - s3*x3 + y3 - y1)) /. (float_of_int (s1 - s3))
(* This evaluates the given curve at the point x. It returns the
* pair (s',y) where y is the value, and s' is the new curve with the
* initial part that is "to the left" of x removed. *)
let delete_to_max s x =
let rec loop first_val first s =
(* first_val is the value using first, the 1st of s. s is non-empty *)
let s1 = remove first s in
if is_empty s1 then (s,first_val) else (
let firsts1 = min_elt s1 in
let firsts1_val = eval firsts1 x in
if firsts1_val >= first_val then loop firsts1_val firsts1 s1 else (s,first_val)
)
in
let first = min_elt s in
loop (eval first x) first s
(* Adds a new line to the given curve. Returns the new curve. *)
let add_new_line t s =
let rec scan_to_left s1 =
if is_empty s1 then s1 else
let l1 = max_elt s1 in
let s2 = remove l1 s1 in
if is_empty s2 then s1 else
let l2 = max_elt s2 in
if (xint l2 t >= xint l1 t) then scan_to_left s2 else s1
in
let rec scan_to_right s1 =
if is_empty s1 then s1 else
let l1 = min_elt s1 in
let s2 = remove l1 s1 in
if is_empty s2 then s1 else
let l2 = min_elt s2 in
if (xint l2 t <= xint l1 t) then scan_to_right s2 else s1
in
(* This is the same as split, except that the boolean "present" is
* replaced by either None, or Some k, where k is the key in the set that
* has the same slope field as the splitting element. *)
let supersplit t s =
let (left,present,right) = split t s in
if present then (left, Some t, right) else
let (sl0,_,_) = t in
let (left,lmat) = if is_empty left then (left,None) else
let lm = max_elt left in
let (sl,_,_) = lm in
if sl=sl0 then (remove lm left, Some lm) else (left,None)
in
let (right,rmat) = if is_empty right then (right,None) else
let rm = min_elt right in
let (sl,_,_) = rm in
if sl=sl0 then (remove rm right, Some rm) else (right,None)
in
match (lmat,rmat) with
| (None,None) -> (left,None,right)
| (Some v,None) | (None,Some v) -> (left, Some v, right)
| (_,_) -> failwith "duplicate slope"
in
let (left,data,right) = supersplit t s in
let left = scan_to_left left in
let right = scan_to_right right in
let include_t () = union left (add t right) in
match (is_empty left, data, is_empty right) with
| (_,Some v,_) ->
if eval t 0 <= eval v 0 then s else include_t ()
| (true,_,_) | (_,_,true) -> include_t ()
| (_,_,_) ->
let lm = max_elt left in
let rm = min_elt right in
if xint lm t < xint rm t then include_t () else union left right
let solve cc dd mach =
let s = List.fold_left
(fun s (d,p,r,g) ->
let (s,y) = delete_to_max s d in
if y < p then s else add_new_line (g,d+1,y-p+r) s)
(singleton (0, 0, cc))
(List.sort Pervasives.compare mach)
in
let (s,y) = delete_to_max s (dd+1) in
y
let read_int () =
Scanf.bscanf Scanf.Scanning.stdib " %d " (fun x -> x)
let rec solve_rest case =
let nn = read_int() in
let cc = read_int() in
let dd = read_int() in
if nn>0 then
let rec loop i accum =
if i=nn then accum else begin
let d = read_int() in
let p = read_int() in
let r = read_int() in
let g = read_int() in
loop (i+1) ((d,p,r,g)::accum)
end
in
let mach = loop 0 [] in
Printf.printf "Case %d: %d\n" case (solve cc dd mach);
solve_rest (case+1)
;;
solve_rest 1