Maximize Rating

题目描述

Takahashi 参加了 $N$ 次比赛，第 $i$ 次比赛的表现为 $P_i$。
他想从这些比赛中选择若干场（至少一场），并使根据这些比赛结果计算的他的 rating 最大化。 通过最优选择比赛，求他能获得的最大可能 rating。 这里，Takahashi 的 rating $R$ 按如下方式计算，其中 $k$ 是被选择的比赛数，$(Q_1, Q_2, \ldots, Q_k)$ 是被选择比赛的表现，按他参赛的顺序：

输入格式

输入从标准输入按照以下格式给出： $N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

输出 Takahashi 能获得的最大可能 rating。
若输出与真实值的绝对或相对误差至多为 $10^{-6}$，则认为是正确的。

3
1000 600 1200

256.735020470879931

3
600 1000 1200

261.423219407873376

1
100

-1100.000000000000000

提示

$1\leq N\leq 5000$ $1\leq P_i\leq 5000$ 所有输入值均为整数。如果 Takahashi 选择第 1 和第 3 场比赛，他的 rating 将是： $\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502...$。 这是可能得到的最大 rating。
当选择第 1、第 2 和第 3 场比赛时，rating 达到最大值。
rating 也可能为负。

标签: AtCoder|abc327E

来源

AtCoder|abc327E