Submission #969050

#	Time	Username	Problem	Language	Result	Execution time	Memory
969050		happy_node	Seesaw (JOI22_seesaw)	C++17	34 / 100	2 ms	604 KiB

seesaw

#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 / 1
• Subtask 2: 33 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33