ABC 401-500/ABC448B - Pepper Addiction - 競技プログラミング用 知識集積所

---

問題

ABC448B

必要知識

A問題レベルのものは省略

• 貪欲法（アルゴリズム系）※

考え方

入力例1の説明では料理2にコショウをあえてかけない選択をしているが、これはコショウ2が4gしかないのを料理2,5,7のどこに使っても合計最大量がかわらないためである。
逆に言えば、最大値を求めるだけでいいなら、後に同じコショウを使えるなど考えずに、その場で使えるだけ使ってしまってよい。（貪欲法※）

それに気づけば、あとは問題の指示通りに前から順に料理にコショウをかけるシミュレーションをやるだけ。
その料理にかけられる量と該当コショウの残量のうち小さい方が、その料理にかけるコショウの量である。

解答例

解答例

注意点

別解