fork download 
  1. #include <bits/stdc++.h>  
  2.  
  3. using namespace std;  
  4.  
  5. #ifdef LOCAL  
  6. #include "debug.h"  
  7. #else  
  8. #define debug(...) 42  
  9. #endif  
  10.  
  11. const int N = 2e5 + 5;  
  12.  
  13. int n;  
  14. int a[N];  
  15. long long pf[N];  
  16.  
  17. double qry(int l, int r) {  
  18.   return (double) (pf[r] - pf[l - 1]) / (r - l + 1);  
  19. }  
  20.  
  21. int main() {  
  22.   ios::sync_with_stdio(false); cin.tie(nullptr);  
  23.  
  24.   cin >> n;  
  25.   for (int i = 1; i <= n; ++i) {  
  26.     cin >> a[i];  
  27.     pf[i] = pf[i - 1] + a[i];  
  28.   }  
  29.   double A = qry(1, n);  
  30.   vector<array<double, 2>> cands = {{A, A}};  
  31.   for (int l = 1; l < n; ++l) {  
  32.     int L = 1, R = n - l + 1, p = 0;  
  33.     while (L <= R) {  
  34.       int md = (L + R) / 2;   
  35.       if (qry(md, md + l - 1) < A) {  
  36.         p = md;  
  37.         L = md + 1;  
  38.       } else {  
  39.         R = md - 1;  
  40.       }  
  41.     }  
  42.     cands.push_back({qry(p, p + l - 1), qry(p + 1, p + l)});  
  43.   }  
  44.   sort(cands.begin(), cands.end());  
  45.   double res = 1e9, mx = cands.back()[0];  
  46.   for (auto [x, y] : cands) {  
  47.     res = min(res, mx - x);  
  48.     mx = max(mx, y);  
  49.   }  
  50.   cout << fixed << setprecision(12) << res;  
  51.   return 0;  
  52. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
6
1 2 5 6 8 9
stdout 
1.166666666667
https://ideone.com/ZCkLiO
language:
C++ (gcc 8.3)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!