/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から p_i までの p_i 種類の目がそれぞれ等確率で出ます。
隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。
制約
- 1 ≤ K ≤ N ≤ 200000
- 1 ≤ p_i ≤ 1000
- 入力で与えられる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K p_1 ... p_N
出力
隣接する K 個のサイコロを選んで振ったときに出る目の合計の期待値の最大値を出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
5 3 1 2 2 4 5
出力例 1
7.000000000000
左から 3 番目、4 番目、5 番目のサイコロを振った時、出る目の合計の期待値は 7 となり、これが最大です。
入力例 2
4 1 6 6 6 6
出力例 2
3.500000000000
どのサイコロを選んで振っても、出る目の期待値は 3.5 です。
入力例 3
10 4 17 13 13 12 15 20 10 13 17 11
出力例 3
32.000000000000
Score : 400 points
Problem Statement
We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.
We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.
Constraints
- 1 ≤ K ≤ N ≤ 200000
- 1 ≤ p_i ≤ 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K p_1 ... p_N
Output
Print the maximum possible value of the expected value of the sum of the numbers shown.
Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.
Sample Input 1
5 3 1 2 2 4 5
Sample Output 1
7.000000000000
When we throw the third, fourth, and fifth dice from the left, the expected value of the sum of the numbers shown is 7. This is the maximum value we can achieve.
Sample Input 2
4 1 6 6 6 6
Sample Output 2
3.500000000000
Regardless of which die we choose, the expected value of the number shown is 3.5.
Sample Input 3
10 4 17 13 13 12 15 20 10 13 17 11
Sample Output 3
32.000000000000