이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Bismillahirrahmanirrahim...
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ONLINE_JUDGE
void solve() {
int n;
cin >> n;
vector <int> vec(n +1);
for(int i = 1; i <= n; i++)
cin >> vec[i];
vector <double> can;
for(int i = 1; i <= n; i++) {
i64 sum = 0;
for(int j = i; j <= n; j++) {
sum += vec[j];
can.emplace_back(double(1) * sum / (j - i +1));
}
}
i64 top = accumulate(vec.begin(), vec.end(), 0LL);
double ans = 1E18;
for(double &mx : can) {
i64 sum = top;
double mn = double(1) * sum / n;
if(mn > mx) {
continue;
}
int l = 1, r = n;
while(l < r) {
//cerr << l << " " << r << "\n";
if(sum - vec[l] <= mx * (r - l)) {
sum -= vec[l];
l++;
} else {
sum -= vec[r];
r--;
}
mn = min(mn, double(1) * sum / (r - l +1));
}
//cerr << "# " << mx << " " << mn << "\n";
ans = min(ans, mx - mn);
//cerr << "\n";
}
cout << setprecision(15) << ans;
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
# | 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... |