20991번 - Sky’s the Limit 스페셜 저지다국어

The N citizens of Eagleton have chosen to build their houses in a row along a single street (so that the houses can be numbered from 1 to N, with 1 the leftmost house and N the rightmost). The houses have varying heights, with house i being h_i inches tall.

Unfortunately, all is not well in Eagleton: the citizens have a bit of an envy problem. Every day, one random citizen (the owner of house i, let’s say) emerges from their house and compares their house’s height to the heights of the two neighboring houses. If house i is at least as tall as the average, plus k inches (in other words, if h_i ≥ (h_i−1+h_i+1)/2+ k), the citizen retreats back into their house, satisfied. Otherwise, the citizen remodels their house to have new height (h_i−1+h_i+1)/2+k. (The citizen does this remodeling even if the new height is only a tiny fraction of an inch taller than the old height—like we said, Eagleton has an envy problem.)

The left of house 1 and the right of house N is a nature preserve; the citizens of these houses treat the preserve as a “house” having height zero inches, for the purposes of the above calculations.

The city council of Eagleton is fed up with the constant construction traffic and noise, and has hired you to compute what Eagleton will look like when all of the remodeling is finally over. After some calculations, you discover that it is guaranteed that each house will converge to a final finite height after infinitely many days of the above remodeling process. Print the final height of the house that ends up tallest.

The first line of input consists of an integer N and real number k, separated by a space (1 ≤ N ≤ 100 000; 0 ≤ k ≤ 10²⁰): the number of houses in Eagleton and the number of inches each citizen wants their own house to be taller than the average of their neighbors.

N lines follow. The ith such line (starting at i = 1) contains a real number h_i (0 ≤ h_i ≤ 10²⁰), the initial height (in inches) of house i.

The real numbers in the input may be provided in scientific notation (see for instance Sample Input 2) and will have at most ten digits after the decimal point.

Print the height (in inches) of the tallest house, after all houses have been remodeled over infinitely many days of the process described above. Your answer will be judged correct if the absolute or relative error is within 10⁻⁶.