Untitled
unknown
c_cpp
a year ago
2.0 kB
17
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