座標圧縮とセグメントツリーを使って求めます。

まず、以下の問題が \(i=1,2,...N\) で高速に解ければいいです。

問題 \(X\)

\(i\) 体倒すのに必要なお守りの数の最小値はいくつですか。

これを解くには以下の問題が解ければいいです。

問題 \(Y\)

\(i\) 番目までに出てくるタイプ \(j\) のモンスターの攻撃力の和を \(S_{j}\) とします。 \(S=(S_{1},S_{2},...,S_{M})\) のうち和が \(H\) 未満になるようにいくつか \(S\) の要素を選ぶとします。 選べる要素の数の最大値はいくつですか。

問題 \(Y\) は \(S\) がソート済みならセグメントツリーの max_right を使うことで求めることができます。

\(i\) が \(1\) 増えたとき、 変化する \(S_{j}\) はちょうど \(1\) つです。

よって、全ての \(i\) に対して \(S_{j}\) としてあり得る数は高々 \(N+1\) 通りなので、座標圧縮することで問題 \(X\) が \(O(\log(N))\) で求まるため、全体で \(O(N\log(N))\) で求まります。

実装例 https://atcoder.jp/contests/abc314/submissions/44517181