COCI '14 Contest 7 #5 Prosjek

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 64M

Author:

Problem type

You are given an array of $N$ $N$ integers. Find a consecutive subsequence of numbers of the length at least $K$ $K$ that has the maximal possible average.

Please note: the average of a subsequence is the sum of all the numbers in the subsequence divided by its length.

Input

The first line of input contains two integers $N$ $N$ $(1 \le N \le 3\cdot10^5)$ $(1 \leq N \leq 3 \cdot 10^{5})$ and $K$ $K$ $(1 \le K \le N)$ $(1 \leq K \leq N)$ . The second line of input contains $N$ $N$ integers $a_i$ $a_{i}$ $(1 \le a_i \le 10^6)$ $(1 \leq a_{i} \leq 10^{6})$

Output

The first and only line of output must contain the maximal possible average. An absolute deviation of $\pm0.001$ $\pm 0.001$ from the official solution is permitted.

Scoring

In test cases worth 30% of total points, it will hold that $N$ $N$ is not larger than $5\,000$ $5 000$ .

Sample Input 1

Copy

4 1
1 2 3 4

Sample Output 1

Copy

4.000000

Sample Input 2

Copy

4 2
2 4 3 4

Sample Output 2

Copy

3.666666

Sample Input 3

Copy

6 3
7 1 2 1 3 6

Sample Output 3

Copy

3.333333

Comments

1

Y commented on Aug. 11, 2019, 10:54 p.m.

Please notice that it is expected to output finite number of digits after the decimal.