3045

重さと耐久力のペアからなる物体の配列が与えられるので、最大危険度が一番小さくなるように縦に積みたい。危険度は、上に乗っている重さの合計から耐久力を引いたものである。

まず、N個のものの一番下に入れるときよりも、それ以外の場所に入れる方がその物体に関する危険度は小さくできる。これは上に乗るものの数が減れば、重さが軽くなることより自明である。次に、N個のものの一番下に入れた時の危険度は、N個の重さの合計から自分の重さを引いたものからさらに耐久度を引いたものである。つまり、N個のものの中から、一番下に入れた時の危険度を最小にするものは、重さと耐久力の合計が一番大きいものである。

以上を組み合わせると、一番下にある物体Aを入れた時の危険度よりも他の物体Bを入れた時の危険度が小さいとすると、AをBの下に入れる理由はなくなる。従って、常に一番下には危険度を最小にするように詰め込んでいけば良い。要素数が多いので、あらかじめ、重さと耐久値の合計(この値は常に変化しない)が大きい順にソートしておけば良い。

つまり今までに出てきた自分よりも(昇順の)上辺の高さだけ覚えておけば、上辺の変動が新しい矩形によるものなのかどうかが分かる。サンプルの時点で入力が複数の図形に分かれているケースがあるので、そこに注意して実装するだけ。