AT_abc327_e [ABC327E] Maximize Rating

题目描述

高桥君参加了 $N$ 次比赛，在第 $i$ 次参加的比赛中获得了表现值 $P_i$。
高桥君想从这些比赛中选择（至少一场）若干场比赛，使得根据这些比赛结果计算出来的高桥君的分数最大。

请你求出通过合理选择比赛后，高桥君可能获得的最大分数。

其中，高桥君的分数 $R$ 的计算方式如下：假设高桥君选择了 $k$ 场比赛，且选中的比赛按参加顺序分别为 $(Q_1, Q_2, \ldots, Q_k)$，则

$$R = \frac{\sum_{i=1}^k (0.9)^{k-i} Q_i}{\sum_{i=1}^k (0.9)^{k-i}} - \frac{1200}{\sqrt{k}}$$

输入格式

输入以如下格式从标准输入读入。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

请输出高桥君可能获得的最大分数。
当你的输出与真实值的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

3
1000 600 1200

输出 #1

256.735020470879931

输入输出样例 #2

输入 #2

3
600 1000 1200

输出 #2

261.423219407873376

输入输出样例 #3

输入 #3

1
100

输出 #3

-1100.000000000000000

说明/提示

数据范围

• $1 \leq N \leq 5000$
• $1 \leq P_i \leq 5000$
• 输入均为整数

样例解释 1

当高桥君选择第 $1$ 场和第 $3$ 场比赛时，分数为 $R = \frac{0.9 \times 1000 + 1.0 \times 1200}{0.9 + 1.0} - \frac{1200}{\sqrt{2}} = 256.73502\ldots$，此时分数最大。

样例解释 2

当选择第 $1,2,3$ 场比赛全部时，分数最大。

样例解释 3

分数有可能为负数。

由 ChatGPT 4.1 翻译