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