| 
いろいろ考えたところ、貪欲法でいけそうとなったのでやってみたらうまくいった。
満足度が高い順に、消費期限の日から遡って飲む予定をできるだけいれて行く。すでに予定が入っている日はスキップする。
(なぜなら既に入っているコーヒーの満足度は入れようとしているものより満足度が同じか高いから。)
以上をやればいいが、largeの日数は単純にループで回してたら終わらないくらい多いので、連続する予定を日数に関係ないオーダーで記録する工夫が必要となる。
具体的には、空いてる日を「開始日と長さのリスト」で管理するようにして、そこに予定をまとまて入れるようにする。
空きリストが[(1,5)]なら1日目から5日分空いてるという状態。そこに4日目から前方向に2日分予定を入れると空きリストは[(1,2),(5,1)]となる。
一般的にはリストを後ろから見ていき、置けるところに置いてリストを更新していけばいい。オーダーはリストの長さになる。
1回の予定挿入でリストの要素数は高々1個増えるだけなので、リストの要素数は最大でもコーヒーの種類数程度。なので日数が1e18とかでも現実的な時間で計算できる。
予定を入れられた分だけ満足度を加算していって、全種類入れ終わったらそれが答え。
