Keskiarvo

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<utility>
#include<iomanip>

using namespace std;

typedef pair<int64_t,int64_t> P;

bool vasen(P p1, P p2, P p3) {
  return (p2.first - p1.first)*(p3.second - p1.second) - (p3.first - p1.first)*(p2.second - p1.second) > 0;
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cout << fixed << setprecision(12);
  
  int64_t n;
  cin >> n;
  vector<int64_t> p(n+1);
  for(int64_t i=1;i<=n;i++) {
    int64_t b;
    cin >> b;
    p[i]=p[i-1]+b;
  }

  vector<pair<int64_t,int64_t>> a;
  a.push_back(make_pair(0,0));

  double best=0;

  for(int64_t i=1;i<=n;i++) {
    int c=a.size();
    while(c >= 2 && vasen(a[c-2], a[c-1], make_pair(i, p[i]))) {
      best=max(best,(double)(p[i] - a[a.size()-1].second) / (double)(i - a[a.size()-1].first));
      a.pop_back();
      c--;
    }
    a.push_back(make_pair(i, p[i]));
  }

  cout << best << '\n';
  
  return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group:

Verdict: ACCEPTED