← 返回题目列表

AtCoder · abc327_e

H. 最大化评级

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

分数: 475 点

问题陈述

高桥参加 N 比赛并获得表演 P_i 在 i第 次比赛。
他想从中选择一些(至少一场)比赛,并最大化根据这些比赛结果计算出的评分。

通过最佳选择比赛来找到他可以获得的最大可能评分。

这里是高桥的评分 R 计算如下,其中 k 是所选比赛的数量, (Q_1, Q_2, \ldots, Q_k) 是所选比赛中的表现 按照他参加的顺序:

\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{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

评级也可以是负面的。