Untitled
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