Keskiarvo

#include <bits/stdc++.h>
using namespace std;
 
#define N 100001
 
// sum_1 / amt_1 > sum_2 / amt_2
// sum_1 * amt_2 > sum_2 * amt_1
long ss[N];
 
long sum(int a, int b)
{
	assert(a <= b);
	assert(1 <= a);
	return ss[b] - ss[a - 1];
}
 
int b[N];
 
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		ss[i] = ss[i-1] + x;
	}
	for (int i = 1; i <= n; ++i) {
		b[i] = 1;
		for (;;) {
			int c = i - b[i] + 1;
			if (c == 1) break;
			int j = c - 1 - b[c - 1] + 1;
			long s1 = sum(j, i);
			long s2 = sum(c, i);
			s1 *= i - c + 1;
			s2 *= i - j + 1;
			if (s2 > s1) break;
			b[i] = i - j + 1;
		}
	}
	double res = 0;
	for (int i = 1; i <= n; ++i) {
		double s = sum(i - b[i] + 1, i);
		res = max(res, s / ((double) b[i]));
	}
	printf("%.9f\n", res);
}

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