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 <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const int INF = 1e9;
int n;
int a[MAXN];
int check2(long double l, long double r)
{
llong sum = 0;
for (int i = 1 ; i <= n ; ++i)
{
sum += a[i];
}
int lPtr = 1, rPtr = n;
while (lPtr <= rPtr)
{
if (sum / (double)(rPtr - lPtr + 1) < l || sum / (double)(rPtr - lPtr + 1) > r)
{
return false;
}
if (lPtr == rPtr)
{
break;
}
if ((sum - a[rPtr]) / (double)(rPtr - lPtr) >= l)
{
sum -= a[rPtr];
rPtr--;
} else
{
sum -= a[lPtr];
lPtr++;
}
}
return true;
}
bool check(long double w)
{
for (int i = 1 ; i <= n ; ++i)
{
llong sum = 0;
for (int j = i ; j <= n ; ++j)
{
sum += a[j];
if (check2(sum / (long double)(j - i + 1), sum / (long double)(j - i + 1) + w))
{
return true;
}
}
}
return false;
}
void solve()
{
long double l = 0.0, r = INF, mid;
for (int i = 0 ; i < 100 ; ++i)
{
mid = (l + r) / 2.0;
if (!check(mid)) l = mid;
else r = mid;
}
std::cout << std::fixed << std::setprecision(10) << r << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
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... |