Overview

This problem asks us to choose one contiguous interval of length \(K\), replace all elements in that interval with their average, and then minimize the resulting “maximum temperature.” We efficiently compute the maximum value after the operation for every possible choice of \(l\), and take the minimum.

Analysis

The operation only changes the selected interval \([l,\,l+K-1]\), where all values become the same (the average). Therefore, the maximum value after the operation is the larger of:

• Inside the interval: the average \(\displaystyle \text{avg}(l)=\frac{F_l+\cdots+F_{l+K-1}}{K}\)
• Outside the interval: values remain unchanged, so the maximum outside the interval

In other words: [ \max_i F’i \;=\; \max\Bigl(\text{avg}(l),\;\max{i \notin [l,l+K-1]} F_i\Bigr) ]

Why the Naive Approach Fails

If for each \(l\) we: - Compute the interval sum in \(O(K)\) each time, and - Search for the maximum outside the interval in \(O(N)\) each time,

the worst case becomes \(O(N^2)\), which will certainly TLE for \(N\le 10^6\).

How to Solve It

• Interval average: By updating the interval sum with a sliding window, each \(l\) takes \(O(1)\)
• Maximum outside the interval: By precomputing “prefix maximum” and “suffix maximum,” each \(l\) takes \(O(1)\)

This brings the overall complexity down to \(O(N)\).

Algorithm

1. Read array \(F\). Simultaneously compute the sum of the first interval (\(l=1\)): \(ws=F_1+\cdots+F_K\).
2. Build prefix maximum:
   [ \text{pre}[i] = \max(F_1,\dots,F_i)\quad (i=1..N),\;\text{pre}[0]=- \infty ] This gives us “maximum to the left of the interval (\(1..l-1\))” as \(\text{pre}[l-1]\) (in the code, \(\text{pre}[l]\) is used due to 0-indexing).
3. Build suffix maximum:
   [ \text{suf}[i] = \max(F_i,\dots,F_N)\quad (i=1..N),\;\text{suf}[N+1]=-\infty ] This gives us “maximum to the right of the interval (\(l+K..N\))” as \(\text{suf}[l+K]\) (0-indexed in the code).
4. For each \(l\) (0-indexed, \(l=0..N-K\)):
   • Average \(\text{avg} = ws / K\)
   • Maximum outside interval \(m_{\text{out}} = \max(\text{pre}[l],\;\text{suf}[l+K])\)
   • Maximum after operation is \(\max(\text{avg},\;m_{\text{out}})\)
   • Update the overall minimum
   • Sliding window update for the next \(l\):
     [ ws \leftarrow ws + F_{l+K} - F_l ]
5. Output the computed minimum as a real number.

Concrete Example (Intuition)

Given \(F=[1,10,2,8,4],\;K=3\): - \(l=1\): interval is \([1,10,2]\), average is \(13/3\approx4.33\), outside is \([8,4]\) with maximum \(8\)
→ maximum after operation is \(\max(4.33,8)=8\) - \(l=2\): interval is \([10,2,8]\), average is \(20/3\approx6.67\), outside is \([1,4]\) with maximum \(4\)
→ maximum after operation is \(\max(6.67,4)=6.67\)

In this way, we can evaluate each choice simply by comparing the “average” and the “maximum outside the interval.”

Complexity

• Time complexity: \(O(N)\) (prefix/suffix construction is \(O(N)\), scanning all \(l\) is also \(O(N)\))
• Space complexity: \(O(N)\) (storing \(F\), prefix, and suffix)

Implementation Notes

• Computing the maximum outside the interval: When the interval is \([l,\,l+K-1]\), the outside is “left: \([0,l-1]\)” and “right: \([l+K,N-1]\).” Each is obtained in \(O(1)\) from prefix/suffix.

• The average is a real number, so compute it as ws / float(K) (no truncation needed).

• Since \(N=10^6\) can be large, in Python it is advisable to use fast input (sys.stdin.buffer.read()) and array('q') (64-bit integers) for stability.

  Source Code

import sys
from array import array

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        sign = 1
        if data[idx] == 45:  # '-'
            sign = -1
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return sign * num

    N = next_int()
    K = next_int()

    F = array('q')
    appendF = F.append

    ws = 0
    for i in range(N):
        x = next_int()
        appendF(x)
        if i < K:
            ws += x

    NEG_INF = -(1 << 60)

    pre = array('q')
    pre_append = pre.append
    pre_append(NEG_INF)
    m = NEG_INF
    for x in F:
        if x > m:
            m = x
        pre_append(m)

    suf = array('q', [NEG_INF]) * (N + 1)
    m = NEG_INF
    for i in range(N - 1, -1, -1):
        x = F[i]
        if x > m:
            m = x
        suf[i] = m
    suf[N] = NEG_INF

    best = float('inf')
    Kf = float(K)
    NK = N - K

    for l in range(NK + 1):
        avg = ws / Kf
        mout = pre[l]
        rmax = suf[l + K]
        if rmax > mout:
            mout = rmax
        val = float(mout) if mout > avg else avg
        if val < best:
            best = val
        if l < NK:
            ws += F[l + K] - F[l]

    sys.stdout.write(f"{best:.10f}\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.