P2466 [SDOI2008] Sue's Little Balls

Sue and Sandy have recently become obsessed with a computer game. The story takes place above a beautiful, mysterious, and thrilling sea. Sue has a small, light boat. However, her goal is not to be a pirate, but to collect colorful eggs floating in the air. Sue has a secret weapon: as long as she rows her boat to a position directly beneath an egg and uses the secret weapon, she can collect that egg instantly. Each egg has a charm value that decreases as the egg falls in the air over time. To score more points, Sue must collect the egg when its charm value is high. If an egg falls into the sea, its charm value becomes a negative number, but that does not dampen Sue's interest, because each egg is unique, and Sue hopes to collect them all. Sandy is not as romantic as Sue. He wants to get as many points as possible. To solve this, he abstracts the game into the following model: Approximate the sea surface as the $x$-axis and set up a vertical Cartesian coordinate plane. Sue's initial position is on the $x$-axis. Initially there are $N$ eggs in the air. For the $i$-th egg, its initial position is the integer coordinate $(x_{i}, y_{i})$. After the game starts, it falls uniformly along the negative $y$-axis with speed $v_{i}$ units of distance per unit time. Sue's initial position is $(x_{0}, 0)$. Sue can move along the positive or negative direction of the $x$-axis, at speed $1$ unit of distance per unit time. Collecting an egg with the secret weapon is instantaneous, and the score equals one-thousandth of the egg's current $y$-coordinate. Now, Sue and Sandy ask for your help. To satisfy both of their goals, you decide to collect all the eggs while achieving the highest possible total score.

The first line contains two integers $N$, $x_{0}$ separated by a space, representing the number of eggs and Sue's initial position. The second line contains $N$ integers $x_{i}$ separated by spaces. The $i$-th number is the initial $x$-coordinate of the $i$-th egg. The third line contains $N$ integers $y_{i}$ separated by spaces. The $i$-th number is the initial $y$-coordinate of the $i$-th egg. The fourth line contains $N$ integers $v_{i}$ separated by spaces. The $i$-th number is the speed at which the $i$-th egg falls uniformly along the negative $y$-axis.

Output a real number, rounded to three decimal places: the maximum score achievable while collecting all the eggs.

For 30% of the testdata, $N \leq 20$. For 60% of the testdata, $N \leq 100$. Constraints: for 100% of the testdata, $-10^4 \leq x_{i}, y_{i} \leq 10^4$, $0 \leq v_{i} \leq 10^4$, $N \leq 1000$. Translated by ChatGPT 5