ABC144 E - Gluttony (500)
最初の考え
最大値では無く合計値を最小化すると誤読していた
消化コストを減らす場合、食べにくさが大きいものを食べる人のを減らすのが常に最大効率
$ A_iを昇順に$ F_iを降順に並べ、$ A_iの先頭からコストを減らしていくのが最適
誤読後
$ dp[i番目まで][j減らした] を持つのは$ k \le 10^{18}なので無理
最小値をxにできるかを二分探索で求める
それぞれの$ A_i毎にx以下の時間にできように消化コストを減らす
使うコストがkを超えた場合は達成不可能
二分探索が$ O(\log K)、一回のシミュレーションが$ O(N)なので全体で$ O(N \log K)