No.1139 Slime Race
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
eSeF
nok0