P5413 [YNOI2019] Cycling

Xiaoming needs to ride a bicycle through $n$ road segments every morning to get to class. The length of the $i$-th segment is $w_i (m)$, and the speed limit is $s_i (m/s)$ (the riding speed on the road cannot exceed the speed limit). The maximum absolute value of acceleration is $a_i (m/s^{2})$ (he can either speed up or slow down). The initial speed is $0 (m/s)$. Your task is to compute the minimum time for Xiaoming to pass these $n$ segments.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, representing the number of test cases. Then follow $T$ test cases, each in the following format: Each test case contains $n+1$ lines. The first line contains a positive integer $n$, representing that there are $n$ road segments. The next $n$ lines each contain three positive integers $w_i, s_i, a_i$, representing the length, the speed limit, and the maximum absolute acceleration of the $i$-th segment, respectively.

Output $T$ lines, corresponding to the answers for the $T$ test cases. That is, the minimum time Xiaoming needs to pass the $n$ road segments (your answer is accepted as long as the absolute error from the standard answer is within $10^{-5}$).

For $60\%$ of the testdata: $0 < n \le 60$. For $80\%$ of the testdata: $0 < n \le 80$. For $100\%$ of the testdata: $0 < n \le 10^{2}, w_i, s_i, a_i \le 10$. Translated by ChatGPT 5