제출 #601894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601894		model_code	Seesaw (JOI22_seesaw)	C++17	100 / 100	105 ms	11672 KiB

seesaw

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rrep(i,l,r) for(int i=l;i<=r;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define unq(x) sort(all(x));x.erase(unique(all(x)),x.end())
//#define mod 1000000007
#define mod 998244353
//ll mod;
#define ad(a,b) a=(a+b)%mod;
#define mul(a,b) a=a*b%mod;
void readv(vector<ll> &a,ll n){
	rep(i,n){
		ll x;
		cin>>x;
		a.push_back(x);
	}
}
void outv(vector<ll> &a,ll n){
	rep(i,n){
		if(i>0)cout<<" ";
		cout<<a[i];
	}
	cout<<"\n";
}
ll po(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
ll gcd(ll a,ll b){
	return (b?gcd(b,a%b):a);
}
#define FACMAX 200010
ll fac[FACMAX],inv[FACMAX],ivf[FACMAX];
void initfac(){
	fac[0]=ivf[0]=inv[1]=1;
	for(ll i=1;i<FACMAX;i++)fac[i]=fac[i-1]*i%mod;
	for(ll i=1;i<FACMAX;i++){
		if(i>1)inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
		ivf[i]=po(fac[i],mod-2);
	}
}
ll P(ll n,ll k){
	if(n<0||n<k)return 0;
	return fac[n]*ivf[n-k]%mod;
}
ll C(ll n,ll k){
	if(k<0||n<k)return 0;
	return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
}
ll H(ll n,ll k){
	return C(n+k-1,k);
}

struct st{
    double ave;
    ll l,r;
    bool operator<(const st&key)const{
        return this->ave<key.ave;
    }
	bool operator>(const st&key)const{
        return this->ave>key.ave;
    }
};

ll n,a[200010],rui[200010];
double ave(ll l,ll r){
	return (rui[r+1]-rui[l])/(double)(r-l+1);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
    rep(i,n)cin>>a[i];
	rui[0]=0;
	rep(i,n)rui[i+1]=rui[i]+a[i];
	priority_queue<st,vector<st>,greater<st> >pq;
	double c=ave(0,n-1);
	ll l=0,r=n-1;
	while(1){
		pq.push((st){ave(l,r),l,r});
		if(l==r)break;
		if(ave(l+1,r)<=c)l++;
		else r--;
	}

    double ans=2e9;
    double ma=c;
    while(1){
		ll ls=pq.top().l,rs=pq.top().r;
		double aves=pq.top().ave;
		double range=ma-aves;
        chmin(ans,range);
        if(rs==n-1)break;
		pq.pop();
		pq.push((st){ave(ls+1,rs+1),ls+1,rs+1});
        chmax(ma,ave(ls+1,rs+1));
    }
    cout<<fixed<<setprecision(9)<<ans<<"\n";
}

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