oj.uz

Submission #969050

# Submission time Handle Problem Language Result Execution time Memory
969050 2024-04-24T12:34:53 Z happy_node Seesaw (JOI22_seesaw) C++17
34 / 100
 2 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=105;
int N;
int A[MX];

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

	cin>>N;
	for(int i=1;i<=N;i++) cin>>A[i];

	vector<double> v;

	for(int l=1;l<=N;l++) {
		ll sum=0;
		for(int r=l;r<=N;r++) {
			sum+=A[r];
			v.push_back((double)sum/(r-l+1));
		}
	}

	sort(v.begin(),v.end());

	ll sum=0;
	for(int i=1;i<=N;i++) sum+=A[i];

	double ans=2e9;

	for(auto x:v) {
		ll l=1,r=N,s=sum,k=N;
		double mx=(double)s/k;
		if(mx<x) continue;

		while(l<r) { 
			double av=(double)(s-A[r])/(k-1);
			if(av>=x) {
				mx=max(mx,av);
				s-=A[r];
				k--;
				r--;
			} else {
				av=(double)(s-A[l])/(k-1);
				mx=max(mx,av);
				s-=A[l];
				k--;
				l++;
			}
		}
		ans=min(ans,mx-x);
	}

	cout<<fixed<<setprecision(10)<<ans<<'\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 456 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Runtime error 1 ms 604 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Runtime error 1 ms 604 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -