Dice in Line

题目描述

我们有 $N$ 个骰子从左到右排列。第 $i$ 个骰子在掷时以相等的概率显示 $1$ 到 $p_i$ 的数字。 我们将选择 $K$ 个相邻的骰子，独立掷每个骰子，并计算显示数字的和。求该和的期望值的最大可能值。

输入格式

输入按下列格式从标准输入给出： $N$ $K$ $p_1$ ... $p_N$

输出格式

输出显示数字之和的期望值的最大可能值。 当你的输出与我们的答案的绝对或相对误差至多为 $10^{-6}$ 时，将被视为正确。

5 3
1 2 2 4 5

7.000000000000

4 1
6 6 6 6

3.500000000000

10 4
17 13 13 12 15 20 10 13 17 11

32.000000000000

提示

$1 ≤ K ≤ N ≤ 200000$ $1 ≤ p_i ≤ 1000$ 输入中的所有值均为整数。当我们掷从左数第三、第四和第五个骰子时，显示数字之和的期望值为 $7$。这是我们能达到的最大值。
无论我们选择哪个骰子，显示数字的期望值都是 $3.5$。

标签: AtCoder|abc154D

来源

AtCoder|abc154D