Submission #925346

#TimeUsernameProblemLanguageResultExecution timeMemory
925346boris_mihovSeesaw (JOI22_seesaw)C++17
0 / 100
1 ms604 KiB
#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; } int opt[MAXN]; 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) { opt[i] = n + 1; long double currAns = 1e18; for (int j = i ; j <= n ; ++j) { if (calc(i, j) > calc(1, n)) break; long double res = check(calc(i, j) - EPS); if (currAns > res) { currAns = res; opt[i] = j; } } ans = std::min(ans, currAns); } for (int i = 1 ; i < n ; ++i) { assert(opt[i] <= opt[i + 1]); } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...