Submission #920566

# Submission time Handle Problem Language Result Execution time Memory
920566 2024-02-02T17:57:36 Z amirhoseinfar1385 Seesaw (JOI22_seesaw) C++17
Compilation error
0 ms 0 KB
#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;
}

Compilation message

seesaw.cpp: In function 'long double calmian(int, int)':
seesaw.cpp:11:15: error: expected ';' before '}' token
   11 |   return 1e9+5
      |               ^
      |               ;
   12 |  }
      |  ~