AT_agc023_d [AGC023D] Go Home

[problemUrl]: https://atcoder.jp/contests/agc023/tasks/agc023_d $ N $ 棟のマンションが数直線上に並んでおり、$ 1 $ から $ N $ までの番号がついています。 マンション $ i $ は座標 $ X_i $ の位置にあります。 また、AtCoder 社は座標 $ S $ の位置にあります。 AtCoder 社の社員は皆、$ N $ 棟のうちいずれかのマンションに住んでいます。 マンション $ i $ に住んでいる社員の人数は $ P_i $ です。 いま、AtCoder 社の社員全員が、一斉に帰宅しようとしています。 彼らは仕事で疲れているため、AtCoder 社の所有するバスでの帰宅を望んでいます。 AtCoder 社の所有するバスは $ 1 $ 台しかありませんが、社員全員を乗せることができます。 このバスは、社員全員を乗せて座標 $ S $ から出発し、次のようなルールで動きます。 - バスに乗っている全員（このバスは自動運転であり、運転手はいないものとする）で、正の方向へ進むか負の方向へ進むかの投票を行う。 各社員 $ 1 $ 票ずつ投票し、棄権は許されない。 その後、得票数の多い方向へ、距離 $ 1 $ だけ移動する。 なお、得票数が同じ場合は、負の方向へ移動する。 もし移動した後の座標にマンションがあるなら、そこに住む社員全員が降りる。 - バスに社員が乗っている限り、上の操作を繰り返す。 具体例については、入出力例 $ 1 $ の説明を参照してください。 バスは、距離 $ 1 $ 進むのにちょうど $ 1 $ 秒かかります。 また、投票や降車にかかる時間は無視できます。 AtCoder 社の社員は全員、自分がバスを降りるまでの時間を最小化するように投票します。 厳密にいうと、ある投票の際には、各社員は、バスがどちらに動いたとき自分の帰宅が早いか (社員全員が今後同じ戦略に従うとして) 考えます。 各社員は、この情報をもとに最適な選択を行いますが、バスがどちらの方向に動いても帰宅までの時間が変わらないときは、負の方向へ投票します。 この時、バスが AtCoder 社を出発してから、最後に社員がバスを降りるまでにかかる時間が何秒かを求めてください。 なお、マンションの位置、住人の数、バスの位置が与えられたとき、バスがどのように動くかは一意に定まることが証明できます。 また、有限時間にすべての社員が帰宅することも証明できます。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ S\ \leq\ 10^9 $ - $ 1\ \leq\ X_1\