SOLUTION

经典题。

二分答案，将所有 $a_i$ 减去 $mid$，容易求得是否存在长度足够长且和为正的子段。

实现方法见代码。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int a[101000],s[101000];
int check(int mid){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i]-mid;
    }
    int mx=1e18;
    for(int i=m;i<=n;i++){
        mx=min(mx,s[i-m]);
        if(s[i]>=mx) return 1;
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]*=1000;
    }
    int L=0,R=2e12;
    while(L<R){
        int mid=(L+R+1)>>1;
        if(check(mid)) L=mid;
        else R=mid-1;
    }
    cout<<L<<'\n';
    return 0;
}