問題一覧 > 通常問題

No.1139 Slime Race

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 336
作問者 : eSeF / テスター : nok0
お気に入りにしたユーザー ProblemId : 4800 / 自分の提出
問題文最終更新日: 2020-07-31 19:06:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 259 (順位表) の他の問題:

Problem Statement

A slime race is being held on an infinite number line, and $N$ slimes are participating.
The $i$-th slime is at coordinate $x_i$ at time $0$, and moves in the positive direction at a constant speed $v_i$.

Since the race takes place on a single straight line, slimes may collide during the race.
When multiple slimes are at the same coordinate at some time $t$, those slimes change as follows.

・The slime with the smallest number absorbs all the other slimes, and the absorbed slimes disappear.
 The speed of the slime with the smallest number becomes
 (its speed before absorbing) + (the sum of the speeds of the slimes it absorbed)
 as a result.

Now, for every slime, consider the distance it has run from time $0$ to time $t$, and let $f(t)$ denote the total sum of these distances.

Find the smallest integer $T$ such that $f(T)\ge D$.

Note that a slime that has been absorbed and has disappeared is considered to have stopped running at that moment.

Input

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

[Constraints]
・$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$
・If $i< j$, then $x_i < x_j$
・All inputs are integers.

Output

Output the integer $T$ that satisfies the conditions of the problem statement.

Sample

Sample 1
Input
3 40
2 5 100
6 4 5
Output
3

At $t=\dfrac{3}{2}$, slimes 1 and 2 collide at coordinate 11.
At this moment, slime 2 disappears and the speed of slime 1 becomes $6+4=10$.

Since $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$ and $2< \dfrac{8}{3} < 3$, the smallest integer such that $f(T)\ge 40$ is $3$.

Sample 2
Input
3 9
1 3 7
1 1 1
Output
3

There may be cases where no collision occurs.

Sample 3
Input
1 160
314
159
Output
2

There is only one slime, but this is still called a race.

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