Maximum average segment

#include <bits/stdc++.h>
using namespace std;

int n, d; vector<double> a;

struct Node {
    int left, right; bool f;
};

Node good(double m) {
    vector<double> prefSums(n+1);
    vector<pair<double, int>> minSums(n+1);
    prefSums[0] = minSums[0].first = -m;
    minSums[0].second = 0;
    for(int i = 1; i <= n; i++) {
        prefSums[i] = prefSums[i-1]+a[i-1]-m;
        if(minSums[i-1].first > prefSums[i]) {
            minSums[i] = {prefSums[i], i};
        } else {
            minSums[i] = minSums[i-1];
        }
    }
    int e = d;
    while(e <= n) {
        if(prefSums[e] >= minSums[e-d].first) {
            return {minSums[e-d].second+1, e, true};
        }
        e++;
    }
    return {-1, -1, false};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> d;
    a.resize(n); for(double& i : a) cin >> i;
    double l = 1, r = 1e7+9;
    Node ans;
    for(int i = 0; i < 100; i++) {
        double m = l+(r-l)/2;
        Node p = good(m);
        if(p.f) {
            ans = p;
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans.left << " " << ans.right;
    return 0;
}