This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e3 + 10;
int n, a[maxn];
vector<ld> L;
bool check(ld L, ld R){
//debug(L, R);
ld sum = 0;
for (int i = 1; i <= n; i++){
sum += a[i];
}
int l = 1, r = n;
ld tmp = sum / n;
//debug(tmp);
if (tmp < L || R < tmp) return false;
for (int i = 1; i < n; i++){
if (L <= a[l] && a[r] <= R) return true;
ld tmp1 = (sum - a[l]) / (n-i);
ld tmp2 = (sum - a[r]) / (n-i);
// debug(l, r, tmp1, tmp2);
if (L <= tmp1 && tmp1 <= R){
sum -= a[l];
l++;
}
else if (L <= tmp2 && tmp2 <= R){
sum -= a[r];
r--;
}
else return false;
}
return true;
}
bool check(ld x){
for (auto y: L){
if (check(y, y+x)) return true;
}
return false;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 1; i <= n; i++){
ld sum = 0;
for (int j = i; j <= n; j++){
sum += a[j];
ld tmp = sum / (j-i+1);
L.push_back(tmp);
}
}
sort(all(L));
L.resize(distance(L.begin(), unique(all(L))));
debug(L.size());
ld l = 0, r = 1e9;
for (int i = 1; i <= 100; i++){
ld mid = (l + r) / 2;
// debug(l, r, mid);
if (check(mid)) r = mid;
else l = mid;
}
cout << setprecision(12) << r << '\n';
}
# | 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... |