P17498 [ICPC 2026 Wuhan I] Lottery

月读空间里正在举办一场抽奖活动。 活动奖池中共有 $n$ 个商品，它们的价值分别为 $A_1,A_2,\cdots,A_n$。 辉夜可以进行若干轮抽奖，但至少要进行一轮。在每一轮抽奖中，过程如下： 1. 辉夜需要支付当前的抽奖代价 $c$，随后在 $[1,n]$ 中等概率随机抽取一个整数 $x$，并得知所抽中的商品 $x$。 2. 得知结果后，辉夜面临两个选择： - 留下第 $x$ 个商品并结束整个抽奖活动，此时她将获得价值为 $A_x$ 的商品。 - 放弃当前抽中的商品，进入下一轮抽奖。但是，抽奖的代价会随之提升，下一轮的抽奖代价将会增加 $k$，即更新 $c\leftarrow c+k$。 辉夜将这场抽奖活动的 “利润” 定义为：最终获得商品的价值 $A_x$ 减去她在所有轮次中支付的抽奖代价之和。 假设辉夜足够聪明，并且总是采取最优策略来最大化她的期望利润。请你求出，在最优策略下，辉夜能获得的期望利润是多少？

第一行包含三个整数 $n,c,k$（$1 \le n \le 4\times10^5$，$1 \le c \le 4\times10^5$，$0 \le k \le 4\times10^5$），分别表示奖池中的商品总数、第一轮抽奖的初始代价，以及每重抽一轮代价的增加量。 第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$（$1 \le A_i \le 4\times10^5$），依次表示每个商品的价值。

输出一行包含一个实数，表示辉夜在最优策略下的期望利润。你的答案被认为是正确的，当且仅当你的答案和标准答案的绝对或相对误差不超过 $10^{-6}$。