AT_arc072_d [ARC072F] Dam

[problemUrl]: https://atcoder.jp/contests/arc072/tasks/arc072_d あなたはダムを管理しています。ダムは $ L $ リットルまで水を蓄えることができます。ダムははじめ干からびています。また、毎日夜に好きな量の水を排出することができます。毎日朝にはダムに水が流入しますが、その時水が溢れないようにする必要があります。 $ i $ 日目の朝には $ t_i $ 度の水が $ v_i $ リットル流入することがわかっています。 各日について、あなたはその日の昼にダムにちょうど $ L $ リットルの水がたまっているという条件のもと、その時点でのダムの水温を最大化しようとすると何度になるかふと気になりました。各 $ i $ について水温の最大値を求めてください。ここで、各最大化のための水の排出は独立に考えるものとします。すなわち、$ i $ 日目の水温の最大化のために排出する水の量は、$ j(≠i) $ 日目の水温の最大化のために排出する水の量と異なっていても構いません。 ただし、水温は流れてくる水以外の一切の影響を受けないものとします。特に、$ T_1 $ 度、$ V_1 $ リットルの水と $ T_2 $ 度、$ V_2 $ リットルの水が混ざると $ \frac{T_1*V_1+T_2*V_2}{V_1+V_2} $ 度、$ V_1+V_2 $ リットルの水となり、これ以外で水の体積・温度が変化することはありません。

N/A

N/A

### 制約 - $ 1≦\ N\ ≦\ 5*10^5 $ - $ 1≦\ L\ ≦\ 10^9 $ - $ 0≦\ t_i\ ≦\ 10^9(1≦i≦N) $ - $ 1≦\ v_i\ ≦\ L(1≦i≦N) $ - $ v_1\ =\ L $ - $ L,\ v_i,\ t_i $ は整数である ### Sample Explanation 1 \- $ 1 $ 日目には $ 1 $ 日目に流れ込んだ水のみがあるので、必ず$ 10 $度です。 - $ 1 $ 日目の夜に水を $ 5 $ リットル捨て、$ 2 $ 日目に流入する水と混ざると $ 10 $ リットル、$ 15 $ 度の水が $ 2 $ 日目に蓄えられます。 - $ 1 $ 日目の夜に水を $ 8 $ リットル捨て、$ 2,\ 3 $ 日目に流入する水と混ざると $ 10 $ リットル、$ 13.2 $度の水が $ 3 $ 日目に蓄えられます。 ### Sample Explanation 3 水温は $ 100 $ 度を超えることがありますが、蒸発については考えません。