# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
877822 | frostray8653 | Seesaw (JOI22_seesaw) | C++17 | 2063 ms | 3456 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC optimize("Ofast,unroll-loops,O3")
#include <bits/stdc++.h>
#define int long long
// #define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
using namespace std;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << " "; dbg(b...);}
void ent() {cout << "\n";}
const int mod = 998244353;
// const int mod = 1e9 + 7;
// const int INF = 2e9;
const int INF = 1e18;
/// ------- Initialization End -------
const int N = 200005;
int a[N], pre[N];
double enumerate(int l, int r, double mn, double mx) {
if (l == r)
return mx - mn;
double lres = (double)(pre[r] - pre[l]) / (r - l);
if (lres <= mx) { /// 取左邊的
int ql = l + 1, qr = r;
while (ql + 1 < qr) {
int mid = (ql + qr) >> 1;
if ((double)(pre[r] - pre[mid - 1]) / (r - mid + 1) <= mx)
ql = mid;
else
qr = mid;
}
return enumerate(ql, r, mn, mx);
}
double rres = (double)(pre[r - 1] - pre[l - 1]) / (r - l);
if (rres >= mn) { /// 取右邊的
return enumerate(l, r - 1, mn, mx);
}
return min(enumerate(l + 1, r, mn, lres), enumerate(l, r - 1, rres, mx));
}
signed main() {
IO;
int n;
cin >> n;
FOR(i, 1, n) cin >> a[i];
double tot = 0;
FOR(i, 1, n) tot += a[i];
double ave = tot / n;
FOR(i, 1, n) pre[i] = pre[i - 1] + a[i];
double ans = enumerate(1, n, ave, ave);
cout << fixed << setprecision(10) << ans << "\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |