問題
提出コード
中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツは
となるパーツ番号
の場合です。このような
のうち最小のものをもとめれば、それより大きい
個のパーツはすべて使用できます。
ということで、まずはそれぞれのパーツについて、昇順でソートをしておきます。すると、先ほどのの最小値は二分探索で求めることができます。
そして、に対して使える
のパーツの個数を記録していきます。
さて、を使うと決めたときは、
となるような
の個数です。ということで、先ほどソートをしていたため、こうなるような
の最小値を求めていれば、使える
の区間が決まります。
を使用したときに使える
の個数は先ほど求めていたため、その記録を後ろ側から累積和を求めることで、
で
を決めたときに使える
と
のパーツの組み合わせを求めることができます。