Google Code Jam Japan 2011 予選（2011/10/1 13:00~19:00）

ooo 62th 最下位

各クエリについて，半開区間[left,right)に操作を施していけばよい．
あるいは，ターゲットだけの位置に注目して，クエリを逆から適用すると簡単に書ける．
Ideone.com - AqX9h - Online Java Compiler & Debugging Tool

賞味期限を区間の境界として，区間を逆から見ていく．ある区間において，（コーヒーが残っている限り）満足度が高いコーヒーから順に飲んでいけば，満足度は最大となる．
Ideone.com - JdsiO - Online Java Compiler & Debugging Tool

$g(n)=\max_{a+b=n}(f(a) + f(b))$ とおく．
この時，
$g(0)=0$
$g(2m)=\max(g(m-1)+2,g(m))$
$g(2m+1)=g(m)+1$
が成り立つ．
数学的帰納法を用いれば，
$g(m-1)+2 \geq g(m)$
が成立するため， $g(2m)=g(m-1)+2$
Ideone.com - TE3By - Online Java Compiler & Debugging Tool