分数: 475 点
问题陈述
高桥参加 N 比赛并获得表演 P_i 在 i第 次比赛。
他想从中选择一些(至少一场)比赛,并最大化根据这些比赛结果计算出的评分。
通过最佳选择比赛来找到他可以获得的最大可能评分。
这里是高桥的评分 R 计算如下,其中 k 是所选比赛的数量, (Q_1, Q_2, \ldots, Q_k) 是所选比赛中的表现 按照他参加的顺序:
约束
- 1\leq N\leq 5000
- 1\leq P_i\leq 5000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
打印高桥可以达到的最大可能评级。
如果与真实值的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 1000 600 1200
示例输出 1
256.735020470879931
如果高桥选择第一场和第三场比赛,他的评分将为:
\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502....
这是可能的最大额定值。
示例输入 2
3 600 1000 1200
示例输出 2
261.423219407873376
当第一、第二和第三场比赛全部被选中时,评分最高。
示例输入 3
1 100
示例输出 3
-1100.000000000000000
评级也可以是负面的。