問題一覧 > 通常問題

No.1139 Slime Race

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 254
作問者 : eSeFeSeF / テスター : nok0nok0
13 ProblemId : 4800 / 出題時の順位表
問題文最終更新日: 2020-07-31 19:06:30

問題文

無限に続く数直線上でスライムのレースが行われていて、$N$ 匹のスライムが参加しています。
$i$ 番目のスライムは時刻 $0$ に座標 $x_i$ に居て、 の方向に一定の速さ $v_i$ で進んでいます。

レースは1本の直線上で行われているので、 レース中にスライムたちが衝突することがあります。
ある時刻 $t$ に複数のスライムが同一の座標にいる状態になったとき、 それらのスライムは以下のように変化します。

・番号の一番小さいスライムがその他のスライムを全て吸収し、吸収されたスライムは消滅する。
 番号の一番小さいスライムは、速さが
 (自分の吸収前の速さ)+(自分が吸収したスライムの速さの和)
 に変化する。

さて、全てのスライムについて時刻 $0$ から時刻 $t$ までに走った距離を求め、 それらを足し合わせた総和を $f(t)$ と表します。

$f(T)\ge D$ である最小の整数 $T$ を求めてください。

なお、吸収され消滅したスライムは、その時点で走るのを終了したとみなして下さい。

入力

$N\ \ D$
$x_1\ \cdots \ x_N$
$v_1\ \cdots \ v_N$

【制約】
・$1\le N\le 10^5$
・$1\le D\le 10^9$
・$1\le x_i\le 10^9$
・$1\le v_i\le 10^9$
・$i< j$ ならば $x_i < x_j$
・入力は全て整数である。

出力

問題文の条件を満たす整数 $T$ を出力せよ。

サンプル

サンプル1
入力
3 40
2 5 100
6 4 5
出力
3

$t=\dfrac{3}{2}$ にスライム1と2が座標 11 で衝突します。
このとき、スライム2は消滅し、スライム1の速さは $6+4=10$ になります。

$f(\frac{8}{3})=\{ 6\times \frac{3}{2}+10\times (\frac{8}{3}-\frac{3}{2}) \}+\{4\times \frac{3}{2} \}+\{5\times \frac{8}{3}\}=40$ 、$2< \dfrac{8}{3} < 3$ であるので、$f(T)\ge 40$ となる最小の整数は $3$ です。

サンプル2
入力
3 9
1 3 7
1 1 1
出力
3

衝突が起きない場合もあります。

サンプル3
入力
1 160
314
159
出力
2

スライムが1匹ですが、これもレースと呼びます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。