fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n;
  9.     cin >> n;
  10.     vector<long long> a(n+1);
  11.     vector<long long> pf(n+1,0);
  12.     for(int i=1;i<=n;++i) {
  13.         cin >> a[i];
  14.         pf[i] = pf[i-1]+a[i];
  15.     }
  16.  
  17.     auto qry = [&](int l,int r)->double {
  18.         return (double)(pf[r]-pf[l-1])/(r-l+1);
  19.     };
  20.  
  21.     double A = qry(1,n);
  22.     vector<array<double,2>> cands = {{A,A}};
  23.  
  24.     for(int len=1; len<n; ++len) {
  25.         int L = 1, R = n-len+1, p = 0;
  26.         while(L <= R) {
  27.             int md = (L+R)/2;
  28.             if(qry(md, md+len-1) < A) {
  29.                 p = md;
  30.                 L = md+1;
  31.             } else {
  32.                 R = md-1;
  33.             }
  34.         }
  35.         cands.push_back({qry(p,p+len-1), qry(p+1,p+len)});
  36.     }
  37.  
  38.     sort(cands.begin(), cands.end());
  39.     double res = 1e9, mx = cands.back()[0];
  40.     for(auto [x,y]: cands) {
  41.         res = min(res, mx-x);
  42.         mx = max(mx, y);
  43.     }
  44.  
  45.     cout << fixed << setprecision(10) << res << "\n";
  46.     return 0;
  47. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
6
1 2 5 6 8 9
stdout 
1.1666666667
https://ideone.com/WMq8Ml
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!