简化题意为在数组 $A$ 中找到一个长度不小于 $L$ 的连续子段，且该子段平均值最大。

二分答案，将问题转换为判断平均值 $x$ 是否合法，即是否存在长度不小于 $L$ 的连续子段的平均值 $\geq x$。

我们先把 $A$ 中的每一个数都减去 $x$，问题再次转换为是否存在长度不小于 $L$ 的连续子段的总和 $\geq 0$。

考虑前缀和，$S_i = A_1 + … + A_i$。朴素地可以枚举子段的两端点，运用前缀和进行计算。

但这种做法一定会超时，我们考虑优化。

我们先把答案表示出来。

$\underset{r - l \geq L}\max(A_{l + 1}, A_l + 1, …, A_r) = \underset{L\leq r\leq n}\max(S_r - \underset{0\leq l \leq r - L}\min(S_l))$

我们可以发现 $r$ 每增加 $1$，$l$ 也只会增加 $1$，所以我们不用每次都枚举 $l$，可以维护 $s_l$ 的最小值 $minl$，然后判断当前的 $s_r - minl$ 是否 $\geq 0$ 即可。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, L;
int a[N];
double s[N];
bool check(double x) {
    for (int i = 1; i <= n; i ++) s[i] = a[i] - x;
    for (int i = 1; i <= n; i ++) s[i] += s[i - 1];
    double minn = 0x3f3f3f3f;
    for (int i = 0, j = L; j <= n; i ++, j ++) {
        minn = min(minn, s[i]);
        if (s[j] - minn >= 0) return true;
    }
    return false;
}
int main() {
    double l = 0, r = 0;
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        r = max(r, (double)(a[i]));
    }
    while (r - l > 1e-6) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(r * 1000));
    return 0;
}