P1419 Finding a Segment

Given a sequence $a$ of length $n$, where $a_i$ is the value of the $i$-th element. You need to find the most valuable "segment" in the sequence. A segment is a contiguous subsequence whose length is in $[S, T]$. The most valuable segment is the one with the maximum average value. The average value of a segment equals the total value of the segment divided by the segment length.

The first line contains an integer $n$, the length of the sequence. The second line contains two integers $S$ and $T$, the allowed range of the segment length, i.e., in $[S, T]$. From the 3rd line to line $n+2$, each line contains one integer, the value of each element.

Output a real number with $3$ decimal places, representing the average value of the optimal segment.

Constraints - For $30\%$ of the testdata, $n \le 1000$. - For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le S \le T \le n$, $-{10}^4 \le a_i \le {10}^4$. Source - Adapted by tinylic. Translated by ChatGPT 5