← 返回题目列表

AtCoder · arc128_c

C. 最大点

中文机器翻译题面 查看原题

分数: 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