Submission #921204

#	Time	Username	Problem	Language	Result	Execution time	Memory
921204		PM1	Seesaw (JOI22_seesaw)	C++17	100 / 100	142 ms	16316 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
#define ll long double
#define fr first
#define sc second
const int mxn=2e5+5;
int n,a[mxn];
ll ps[mxn],mx,ans=1e9;
vector<pair<ll,ll>>v;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ps[i]=ps[i-1]+a[i];
	}
	for(int i=1;i<n;i++){
		int L=1,R=n-i+1;
		while(R-L>1){
			int mid=(L+R)/2;
			ll x=(ps[mid+i-1]-ps[mid-1])/(ll)i;
			if(x<=(ps[n]/(ll)n))
				L=mid;
			else
				R=mid;
		}
		ll x=(ps[L+i-1]-ps[L-1])/i,y=(ps[L+i]-ps[L])/(ll)i;
		v.push_back({x,y});
		//cout<<x<<" "<<y<<endl;
	}
	v.push_back({ps[n]/(ll)n,ps[n]/(ll)n});
	sort(v.begin(),v.end());
	mx=v.back().fr;
	for(auto i:v){
		ll L=i.fr,R=mx;
		ans=min(ans,R-L);
		//cout<<L<<" "<<R<<endl;
		mx=max(mx,i.sc);
	}
	cout<<setprecision(10);
	cout<<ans<<'\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33