Google Code Jam Japan 2011 予選 B. 最高のコーヒー
後の日から順に、その日に飲むコーヒーを割り当てていくならば、一番満足度の高いコーヒーを貪欲に飲めば良い。飲むコーヒーが変わるのは、そのコーヒーが無くなるか、他のコーヒーが賞味期限前になった時なので、まとめて計算すると、Largeも間に合う。
# coding: utf-8 class Coffee: def __init__(self,c,t,s): self.c = c self.t = t self.s = s def solve(N,K,C): C += [Coffee(10**20,10**20,0)] ans = 0 while K>0: # 飲むコーヒー s = max((c for c in C if c.c>0 and c.t>=K), key=lambda c: c.s) # 遅くともこの時刻までは飲むコーヒーは変わらない k = max([0,K-s.c]+[c.t for c in C if c.t<K]) ans += s.s*(K-k) s.c -= K-k K = k return ans for t in range(input()): N,K = map(int,raw_input().split()) C = [Coffee(*map(int,raw_input().split())) for i in range(N)] print "Case #%s: %s" % (t+1,solve(N,K,C))