이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const long double EPS = 1e-10;
const int INF = 2e9;
int n;
int a[MAXN];
llong prefix[MAXN];
long double calc(int l, int r)
{
return ((long double)(prefix[r] - prefix[l - 1])) / (r - l + 1);
}
long double check(long double from)
{
long double to = from;
int l = 1, r = n;
while (true)
{
to = std::max(to, calc(l, r));
if (l == r)
{
break;
}
if (calc(l, r - 1) > from)
{
r--;
} else
{
l++;
}
}
return to - from;
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
prefix[i] = prefix[i - 1] + a[i];
}
long double ans = 1e18;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = i ; j <= std::min(n, i + 250) ; ++j)
{
if (calc(i, j) > calc(1, n)) break;
ans = std::min(ans, check(calc(i, j) - EPS));
}
}
std::cout << std::fixed << std::setprecision(10) << ans << '\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... |