Overview

This problem asks us to select one contiguous subarray of length \(K\) from an array of length \(N\), replace all elements within that subarray with the “average value of the subarray,” and minimize the maximum value of the entire array.

By performing appropriate preprocessing (prefix sums and prefix/suffix maximum values), we can compute the maximum value for each chosen subarray in \(O(1)\), solving the problem in \(O(N)\) total time complexity.

---

Analysis

1. Determining the maximum value after the operation

When we select a subarray \([l, l+K-1]\) and perform the smoothing operation, the elements of the array after the operation are divided into two groups:

1. Elements inside the subarray: All replaced by the average value \(\text{avg} = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}\).
2. Elements outside the subarray: Remain unchanged at their original temperatures \(F_i\).

Therefore, the overall maximum value after the operation is the larger of “the maximum value of elements outside the subarray” and “the average value within the subarray”. $\(\text{Maximum after operation} = \max(\text{Maximum outside the subarray}, \text{Average within the subarray})\)$

Since the left endpoint \(l\) of the chosen subarray ranges over \(1 \le l \le N-K+1\), we need to compute the “maximum after operation” for all values of \(l\) and find the minimum among them.

2. Naive approach and its limitations

For each \(l\), if we naively compute the maximum outside the subarray and the average inside the subarray, each computation takes \(O(N)\) time. Since there are \(O(N)\) candidates for \(l\), the total time complexity becomes \(O(N^2)\), which will result in a Time Limit Exceeded (TLE) verdict given the constraint \(N \le 10^6\).

To resolve this, we need techniques (preprocessing) to retrieve both “the average within the subarray” and “the maximum outside the subarray” in \(O(1)\) each.

---

Algorithm

① Speeding up average computation using prefix sums

To quickly compute the sum of the subarray \([l, l+K-1]\), we use prefix sums. By preparing an array \(Sum\) where \(Sum[i] = F_1 + F_2 + \cdots + F_i\) (with \(Sum[0] = 0\)), the subarray sum can be computed in \(O(1)\) as follows: $\(\text{Subarray sum} = Sum[l+K-1] - Sum[l-1]\)\( Dividing this by \)K\( gives the average \)\text{avg}\( in \)O(1)$.

② Speeding up the outside maximum using prefix/suffix maximums

The elements outside the subarray are split into two parts: “the left side \([1, l-1]\)” and “the right side \([l+K, N]\)” of the chosen subarray. To quickly find the maximum in each part, we precompute the following two arrays:

• Prefix maximum \(P\): Maximum from the left end \(P[i] = \max(F_1, F_2, \ldots, F_i)\)
• Suffix maximum \(S\): Maximum from the right end \(S[i] = \max(F_i, F_{i+1}, \ldots, F_N)\)

With these prepared, the maximum outside the subarray can be obtained in \(O(1)\) as follows: $\(\text{Maximum outside the subarray} = \max(P[l-1], S[l+K])\)$

③ Overall procedure

1. Construct the prefix sum array \(Sum\), prefix maximum array \(P\), and suffix maximum array \(S\), each in \(O(N)\).
2. For \(l = 1, 2, \ldots, N-K+1\), compute the following:
   • \(\text{max\_outside} = \max(P[l-1], S[l+K])\)
   • \(\text{avg} = \frac{Sum[l+K-1] - Sum[l-1]}{K}\)
   • \(\text{current\_max} = \max(\text{max\_outside}, \text{avg})\)
3. Output the minimum of \(\text{current\_max}\) over all \(l\).

---

Complexity

• Time complexity: \(O(N)\) The preprocessing (prefix sums, prefix/suffix maximum construction) takes \(O(N)\). The subsequent loop over \(l\) runs \(N-K+1\) times, with each iteration processed in \(O(1)\), so the overall time complexity is \(O(N)\), which is sufficiently fast.

• Space complexity: \(O(N)\) Storing the input and the preprocessing arrays (\(Sum, P, S\)) each require arrays of length \(O(N)\), so the space complexity is \(O(N)\).

---

Implementation Notes

• Handling boundary cases (edge processing): When \(l=1\), the left interval \([1, l-1]\) is empty, and when \(l=N-K+1\), the right interval \([l+K, N]\) is empty. To simplify the process of finding the maximum of such “non-existent intervals,” the code stores a sufficiently small value (such as \(-2 \times 10^{18}\), a value far smaller than the minimum possible temperature \(F_i\)) in \(P[0]\) and \(S[N+1]\). This allows elegant handling of edge cases without needing conditional branches (if statements).

• Types and precision: The sum of temperatures can reach up to \(10^6 \times 10^9 = 10^{15}\), so long long (64-bit integer type) is used to prevent overflow. Additionally, for computing averages and maintaining the minimum value, floating-point numbers with sufficient precision (such as double) are used, and the output specifies a generous number of decimal places.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> F(N);
    for (int i = 0; i < N; ++i) {
        cin >> F[i];
    }

    // P[i]: F[0] から F[i-1] までの最大値
    vector<long long> P(N + 1);
    P[0] = -2e18; 
    for (int i = 0; i < N; ++i) {
        P[i + 1] = max(P[i], F[i]);
    }

    // S[i]: F[i-1] から F[N-1] までの最大値
    vector<long long> S(N + 2);
    S[N + 1] = -2e18;
    for (int i = N - 1; i >= 0; --i) {
        S[i + 1] = max(S[i + 2], F[i]);
    }

    // 累積和
    vector<long long> Sum(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        Sum[i + 1] = Sum[i] + F[i];
    }

    double min_max_val = 1e18; 

    for (int l = 1; l <= N - K + 1; ++l) {
        long long max_outside = max(P[l - 1], S[l + K]);
        double avg = (double)(Sum[l + K - 1] - Sum[l - 1]) / K;
        double current_max = max((double)max_outside, avg);
        if (current_max < min_max_val) {
            min_max_val = current_max;
        }
    }

    cout << fixed << setprecision(12) << min_max_val << "\n";

    return 0;
}

---

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