Submission #920574

#	Time	Username	Problem	Language	Result	Execution time	Memory
920574		amirhoseinfar1385	Seesaw (JOI22_seesaw)	C++17	100 / 100	103 ms	21196 KiB

seesaw

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10;
long long all[maxn],ps[maxn],n;
long double md;
pair<long double,long double>stf[maxn];

long double calmian(int len,int l){
	int r=l+len-1;
	if(r>n){
		return 1e9+5;
	}
	long double ret=ps[r]-ps[l-1];
	ret/=len;
	return ret;
}

void calstf(int ind){
	int low=1,high=n+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(calmian(ind,mid)<=md){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	stf[ind].first=calmian(ind,low);
	stf[ind].second=calmian(ind,high);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>all[i];
		ps[i]=ps[i-1]+all[i];
	}
	md=(long double)ps[n]/n;
	long double mx=md;
	vector<pair<long double,int>>v;
	for(int i=1;i<=n;i++){
		calstf(i);
		v.push_back(make_pair(stf[i].first,i));
	}
	sort(v.rbegin(),v.rend());
	long double res=1e9;
	while((int)v.size()>0){
		//cout<<mx<<" "<<v.back().first<<" "<<v.back().second<<endl;
		res=min(res,mx-v.back().first);
		mx=max(mx,stf[v.back().second].second);
		v.pop_back();
	}
	cout<<setprecision(10)<<fixed<<res<<endl;
}

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