分数: 600 点
问题陈述
给定的是整数 N, M, S,以及一系列 N 整数 A=(A_1,A_2,\cdots,A_N).
考虑制作一系列 N 非负 真实 号码 x=(x_1,x_2,\cdots,x_N) 满足以下所有条件:
- 0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq M,
- \sum_{1 \leq i \leq N} x_i=S.
现在,让我们定义 x as \sum_{1 \leq i \leq N} A_i \times x_i。 找出可能的最大分数 x.
约束
- 1 \leq N \leq 5000
- 1 \leq M \leq 10^6
- 1 \leq S \leq \min(N \times M,10^6)
- 1 \leq A_i \leq 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M S A_1 A_2 \cdots A_N
约束
打印答案。 如果您的输出的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 2 3 1 2 3
示例输出 1
8.00000000000000000000
最优选择是 x=(0,1,2).
示例输入 2
3 3 2 5 1 1
示例输出 2
4.66666666666666666667
最优选择是 x=(2/3,2/3,2/3).
示例输入 3
10 234567 1000000 353239 53676 45485 617014 886590 423581 172670 928532 312338 981241
示例输出 3
676780145098.25000000000000000000