Untitled

 avatar
unknown
c_cpp
a year ago
2.0 kB
6
Indexable
#include <bits/stdc++.h>
using namespace std;

#define Task "RATE"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 1e6 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

int n, k;
int a[N];
int l = -1, r = -1;

bool check(double average) {
    double sum = 0;
    FOR(i, 1, k) sum += a[i] - average;
    if (sum >= 0) {
        l = 1;
        r = k;
        return true;
    }
    double pre = 0, minPre = 0, minL = 1;
    FOR(i, k + 1, n) {
        sum += a[i] - average;
        pre += a[i - k] - average;
        if (minimize(minPre, pre)) minL = i - k + 1;
        if (sum - minPre >= 0) {
            l = minL;
            r = i;
            return true;
        }
    }
    return false;
}

double bs(double lo, double hi) {
    double d = 0.000001;
    while (hi - lo > d) {
        double mid = lo + (hi - lo) / 2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    return lo;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }

    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];

    int minVal = INF, maxVal = 0;
    FOR(i, 1, n) minimize(minVal, a[i]), maximize(maxVal, a[i]);

    cout << fixed << setprecision(6);
    bs(minVal * 1.0, maxVal * 1.0);

    double sum = 0;
    FOR(i, l, r) sum += a[i];
    cout << sum / (r - l + 1);

    return 0;
}


Editor is loading...
Leave a Comment