P17498 [ICPC 2026 Wuhan I] Lottery

A lottery event is being held in the Tsukuyomi. There are $n$ items in the prize pool, and their values are $A_1,A_2,\cdots,A_n$. Kaguya can participate in the lottery for several rounds, but she must participate in at least one round. In each round, the process is as follows: 1. Kaguya needs to pay the current lottery cost $c$, and then an integer $x$ is chosen uniformly at random from $[1,n]$. She learns which item $x$ was drawn. 2. After seeing the result, Kaguya has two choices: - Keep the $x$-th item and end the entire lottery event. In this case, she will obtain the item with value $A_x$. - Give up the currently drawn item and enter the next round of the lottery. However, the lottery cost will increase accordingly, and the cost of the next round will become $c+k$, that is, update $c\leftarrow c+k$. Kaguya defines the “profit” of this lottery event as the value of the finally obtained item $A_x$ minus the sum of the lottery costs she paid in all rounds. Assuming Kaguya is smart enough and always takes the optimal strategy to maximize her expected profit, please find the expected profit she can obtain under the optimal strategy.

The first line contains three integers $n,c,k$ ($1 \le n \le 4\times10^5$, $1 \le c \le 4\times10^5$, $0 \le k \le 4\times10^5$), representing the total number of items in the prize pool, the initial cost of the first lottery round, and the increase in cost for each reroll. The second line contains $n$ integers $A_1,A_2,\cdots,A_n$ ($1 \le A_i \le 4\times10^5$), representing the value of each item.

Output one line containing a real number, representing the expected profit under Kaguya's optimal strategy. Your answer is considered correct if and only if the absolute or relative error between your answer and the standard answer does not exceed $10^{-6}$.