ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

УрКОП 2020

About     Problems     Submit solution     Judge status     Standings
Contest is over

L. Skydiving

Time limit: 3.0 second
Memory limit: 256 MB
Kirill decided to go skydiving. He arrived at a Cartesian coordinate system, in which ground and air are separated by the line y = 0 m, the air is above (in the half-plane y ≥ 0 m), the ground is below. Gravity is directed downwards (in the direction of decrease of coordinate y).
Kirill ascended to the point (x, y) and started falling. He is falling with gravitational acceleration equal to 10 m/s2. Kirill’s starting vertical speed is equal to 0 m/s. But his horizontal speed is fully in his control: at any point in time Kirill can change his horizontal speed to any value between −1 m/s and 1 m/s.
Kirill wants to spend as much time in the air as possible. Luckily for him, there are n clouds in the air. Kirill calculated that i-th cloud is located in the point (xi, yi) and has density ci. If Kirill reaches a point where the i-th cloud is located, he will instantly stop and spend the next ci seconds motionless in that point. After that he will start falling again, starting with a vertical speed of 0 m/s, and will be able to change his horizontal speed again to any value between −1 m/s and 1 m/s.
Find out the longest possible time Kirill could spend falling. He stops falling when he reaches the line y = 0 m.


The first line contains one integer n — amount of clouds (0 ≤ n ≤ 50000).
The second line contains two integers x and y — Kirill’s starting coordinates in meters (−10000 ≤ x ≤ 10000; 1 ≤ y ≤ 10000).
Then n lines follow, i-th of them contains three integers xi, yi and ci — coordinates of a cloud and its density (−10000 ≤ xi ≤ 10000; 0 < yi < y; 1 ≤ ci ≤ 10000). It is guaranteed that all clouds are located in distinct points.


Output one number — the maximum possible duration of falling in seconds. Your answer is considered correct if its absolute or relative error doesn’t exceed 10−4.


0 80
-1 30 2
-1 60 1
0 40 10
1 20 1
1 50 1
100 100
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020
To submit the solution for this problem go to the Problem set: 2157. Skydiving