150C Smart Cheater

解法

まず、各区間についてネコババした時の期待値を求める(O(n))。
（監査に引っかかってもネコババ分は手に入るのに注意。）

次に、各人どの区間ネコババするかを考える。
愚直にやるとO(m*n*n)だが、セグメントツリーを使うことでO(2*n + m*logn)になる。

各セルに{左にくっついてる区間での最大; 右にくっついてる区間での最大; どっちにもくっついてない区間での最大; 全体区間での最大（というか和）}を持たせてる。

木といえば直和！ってことでOCamlでやってみた。
queryはもう少し綺麗に書けるかも。
あと、セグメントツリー自体ライブラリ（具体的にはfunctor）に出来る気がする。

ソースコード

module Std = struct

  module List = struct
    include List
    module L = List
    let map f lst = L.rev (L.rev_map f lst)
    let map2 f l1 l2 = L.rev (L.rev_map2 f l1 l2)
    let each_cons f lst = L.rev_map2 f (L.tl (L.rev lst)) (L.rev (L.tl lst))
    let append x y = List.rev (List.rev_append x y)
  end

  let ( |> ) x f = f x
  let ( <| ) f x = f x
  let ( ~. ) = float_of_int
  let ( ~: ) = int_of_float
  let ( @ ) = List.append

  let rec repeat n f x = if n = 0 then x else repeat (n-1) f (f x)

  let di x = prerr_endline (string_of_int x); x
  let df f = prerr_endline (string_of_float f); f
  let ds s = prerr_endline s; s
    
  let int () = Scanf.scanf "%d%c" (fun x _ -> x)
  let read_int = int
  let float () = Scanf.scanf "%f%c" (fun x _ -> x)
  let read_float = float
  let rec n_int n () = List.rev <| repeat n (fun lst -> int () :: lst) []
  let rec n_float n () = List.rev <| repeat n (fun lst -> float () :: lst) []

end

open Std
module L = List

let max = L.fold_left max neg_infinity

(* entry point *)

let n = int ()
let m = int ()
let c = int ()

let x = n_int n ()

let p = n_int (n-1) () |> L.map (fun x -> ~.x *. 0.01)

let ab = L.rev <| repeat m (fun lst -> let a = int () in let b = int () in (a-1, b-2) :: lst) []

let w = 
  let s = L.each_cons (fun x y -> y-x) x in
    L.map2 (fun pi si -> ~.si /. 2. -. pi *. ~.c) p s |> Array.of_list 

type data = { left:float; right:float; between:float; full:float; }

type tree = 
  | Leaf of data
  | Node of data * int * int * tree * tree

let getdata = function
  | Leaf(data) -> data
  | Node(data,_,_,_,_) -> data

let merge ldata rdata = {
  left  = max [ldata.left; ldata.full; (ldata.full +. rdata.left)];
  right = max [rdata.right; rdata.full; (rdata.full +. ldata.right)];
  between = max [ldata.between; rdata.between; ldata.right; rdata.left; (ldata.right +. rdata.left)];
  full = ldata.full +. rdata.full;  
}

let rec make_tree l r =
  if l = r then
    Leaf({ left = 0.; right = 0.; between = 0.; full = w.(l); })
  else
    let mid = (l+r) / 2 in
    let ltree = make_tree l mid in
    let rtree = make_tree (mid+1) r in
    let ldata = getdata ltree in
    let rdata = getdata rtree in
      Node(merge ldata rdata, l, r, ltree, rtree)

let rec query l r = function
  | Leaf(data) ->
     data
  | Node(data, start, finish, ltree, rtree) ->
      if l = start && r = finish then
	data
      else 
	let mid = (start+finish)/2 in
	  if r <= mid then
	    query l r ltree
	  else if l > mid then 
	    query l r rtree
	  else 
	    let ldata = query l mid ltree in
	    let rdata = query (mid+1) r rtree in
	      merge ldata rdata

let segtree = make_tree 0 (n-2)

let () = 
  L.map (fun (a,b) -> let r = query a b segtree in max [r.left; r.right; r.between; r.full]) ab
  |> L.fold_left (+.) 0.
  |> print_float

追記: モジュール化してみた

どこが本質なのかまだちょっと自信が無いので不適切かも

module Std = struct

  module List = struct
    include List
    module L = List
    let map f lst = L.rev (L.rev_map f lst)
    let map2 f l1 l2 = L.rev (L.rev_map2 f l1 l2)
    let each_cons f lst = L.rev_map2 f (L.tl (L.rev lst)) (L.rev (L.tl lst))
    let append x y = List.rev (List.rev_append x y)
  end

  let ( |> ) x f = f x
  let ( <| ) f x = f x
  let ( ~. ) = float_of_int
  let ( ~: ) = int_of_float
  let ( @ ) = List.append

  let rec repeat n f x = if n = 0 then x else repeat (n-1) f (f x)

  let di x = prerr_endline (string_of_int x); x
  let df f = prerr_endline (string_of_float f); f
  let ds s = prerr_endline s; s
    
  let int () = Scanf.scanf " %d" (fun x -> x)
  let read_int = int
  let float () = Scanf.scanf " %f" (fun x -> x)
  let read_float = float
  let rec n_int n () = List.rev <| repeat n (fun lst -> int () :: lst) []
  let rec n_float n () = List.rev <| repeat n (fun lst -> float () :: lst) []

end

module Segtree = struct
  module type Builder = sig 
    type data
    val merge : data -> data -> data
    val terminal : int -> data
  end

  module Make = functor(B : Builder) -> struct
    type t =
      |	Leaf of B.data
      | Node of B.data * int * int * t * t

    let getdata = function
      | Leaf(data) -> data
      | Node(data,_,_,_,_) -> data

    let rec make l r =
      if l = r then
	Leaf(B.terminal l)
      else
	let mid = (l+r) / 2 in
	let ltree = make l mid in
	let rtree = make (mid+1) r in
	let ldata = getdata ltree in
	let rdata = getdata rtree in
	  Node(B.merge ldata rdata, l, r, ltree, rtree)

    let rec query l r = function
      | Leaf(data) ->
	  data
      | Node(data, start, finish, ltree, rtree) ->
	  if l = start && r = finish then
	    data
	  else 
	    let mid = (start+finish)/2 in
	      if r <= mid then
		query l r ltree
	      else if l > mid then 
		query l r rtree
	      else 
		let ldata = query l mid ltree in
		let rdata = query (mid+1) r rtree in
		  B.merge ldata rdata

  end

end

(* entry point *)

open Std
module L = List

let max = L.fold_left max neg_infinity

let n = int ()
let m = int ()
let c = int ()

let x = n_int n ()

let p = n_int (n-1) () |> L.map (fun x -> ~.x *. 0.01)

let ab = L.rev <| repeat m (fun lst -> let a = int () in let b = int () in (a-1, b-2) :: lst) []

let w = 
  let s = L.each_cons (fun x y -> y-x) x in
    L.map2 (fun pi si -> ~.si /. 2. -. pi *. ~.c) p s |> Array.of_list 

module A = struct

  type data = { left:float; right:float; between:float; full:float; }

  let terminal i = { left = 0.; right = 0.; between = 0.; full = w.(i); }

  let merge ldata rdata = {
    left  = max [ldata.left; ldata.full; (ldata.full +. rdata.left)];
    right = max [rdata.right; rdata.full; (rdata.full +. ldata.right)];
    between = max [ldata.between; rdata.between; ldata.right; rdata.left; (ldata.right +. rdata.left)];
    full = ldata.full +. rdata.full;  
  }

end

module MySegtree = Segtree.Make(A)

open A

let segtree = MySegtree.make 0 (n-2)

let to_ans data = max [data.left; data.right; data.between; data.full]

let () = 
  L.map (fun (a,b) -> MySegtree.query a b segtree |> to_ans) ab
  |> L.fold_left (+.) 0.
  |> print_float

出典

http://codeforces.com/contest/150/problem/C