問題
考察
飲む薬の錠数がK錠以下になるのは何日目か求めてくださいという問題です。1日目はすべての薬を飲むことになりますが、次第に飲む薬の錠数が減っていきます。1日目から順にシミュレートしていきたいところです。ですが、$a_i$は$10^9$まで値をとるので、計算量的に間に合いそうにありません。そこで、薬を飲む錠数が減る日にちのみに注目してシミュレートするようにしていきましょう。薬を飲む錠数が減るタイミングは各種類の$a_i + 1$日目です。このときに現在飲んでいる錠数から$b_i$錠減らします。これで$K$錠以下になっているかを確かめると良いです。1日目に飲む薬の錠数は各種類の全ての錠数を合計すればいいですし、薬の種類を$a_i + 1$が小さい順にソートさせておけば薬を減らす順に薬を取り出すことができます。
これらによって十分間に合う計算量でシミュレートできそうです。実装していきましょう。
実装によっては1日目で$K$錠以下しか飲んでいないコーナーケースが出てくることもあります。注意しましょう。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。