Overview

Given a sequence of length \(N\), select \(K\) consecutive elements and replace all of them with the average value of that interval. The problem asks for the minimum possible value of the maximum element in the entire sequence after the operation.

Analysis

Let’s fix the left endpoint index \(i\) (0-indexed, \(0 \leq i \leq N-K\)) of the interval chosen for the operation. When we select the interval \([i, i+K-1]\) and replace it with the average value, the maximum value of the entire sequence after the operation is the maximum of the following three values:

1. Left side of the interval: the maximum of elements from index \(0\) to \(i-1\)
2. Right side of the interval: the maximum of elements from index \(i+K\) to \(N-1\)
3. Within the interval: the average value

If we naively compute this for every \(i\), it takes \(O(N)\) time for each \(i\) to find the sum within the interval and the maximum values on the left and right, resulting in \(O(N^2)\) overall. Since the constraint is \(N \leq 10^6\), this would exceed the time limit (TLE).

Therefore, we perform precomputation (prefix sums and prefix/suffix maximums) so that these three values can be retrieved in \(O(1)\) for each \(i\).

Algorithm

To efficiently compute the three values for each \(i\), we precompute the following three arrays.

1. Prefix Sum

To compute the sum within an interval in \(O(1)\), we prepare the prefix sum \(S\) of array \(F\). Defining \(S[x] = \sum_{j=0}^{x-1} F_j\) (with \(S[0] = 0\)), the sum of the interval \([i, i+K-1]\) is \(S[i+K] - S[i]\). Therefore, the average value is \(\displaystyle \text{avg} = \frac{S[i+K] - S[i]}{K}\).

2. Prefix Max (Cumulative Maximum from the Left)

To compute the maximum value on the left side of the interval in \(O(1)\), we prepare the prefix maximum array \(L\). Define \(L[i] = \max(F_0, F_1, \ldots, F_{i-1})\). This can be constructed in \(O(N)\) by scanning from left to right using the recurrence \(L[i] = \max(L[i-1], F_{i-1})\).

3. Suffix Max (Cumulative Maximum from the Right)

To compute the maximum value on the right side of the interval in \(O(1)\), we prepare the suffix maximum array \(R\). Define \(R[j] = \max(F_j, F_{j+1}, \ldots, F_{N-1})\). This can similarly be constructed in \(O(N)\) by scanning from right to left.

---

With these precomputations, the maximum value after the operation for each \(i\) (\(0 \leq i \leq N-K\)) can be computed in \(O(1)\) as: $\(\max(L[i], R[i+K], \text{avg})\)\( The minimum of this value over all \)i$ is the desired answer.

Complexity

• Time Complexity: \(O(N)\) Building the prefix sum and prefix/suffix maximums takes \(O(N)\). Since determining the maximum for each \(i\) afterwards takes \(O(1)\), the entire loop is also \(O(N)\), which is well within the time limit.
• Space Complexity: \(O(N)\) We use arrays of size \(O(N)\) each to store the prefix sum array \(S\) and the cumulative maximum arrays \(L, R\).

Implementation Notes

• Boundary handling When \(i = 0\), the “left side of the interval” does not exist, and when \(i = N-K\), the “right side of the interval” does not exist. To ensure that the maximum of non-existent parts does not affect the result, we insert a sufficiently small sentinel value (such as \(-10^{18}\)) at the beginning of array \(L\) and at the end of array \(R\).

• Floating-point arithmetic Instead of dividing by \(K\) each time when computing the average, we can precompute inv_K = 1.0 / K and convert the division to multiplication ((S[i+K] - S[i]) * inv_K), which slightly speeds up execution time.

  Source Code

import sys
from itertools import accumulate


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])

    F = list(map(int, input_data[2 : 2 + N]))

    INF = 10**18

    L = [-INF] + list(accumulate(F, max))
    R = list(accumulate(F[::-1], max))[::-1] + [-INF]
    S = [0] + list(accumulate(F))

    ans = INF
    inv_K = 1.0 / K

    for i in range(N - K + 1):
        l_max = L[i]
        r_max = R[i + K]
        avg = (S[i + K] - S[i]) * inv_K
        cur = l_max if l_max > r_max else r_max
        if avg > cur:
            cur = avg
        if cur < ans:
            ans = cur

    print(f"{ans:.12f}")


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.