제출 #997807

#제출 시각아이디문제언어결과실행 시간메모리
997807amirhoseinfar1385Sure Bet (CEOI17_sure)C++17
100 / 100
593 ms3668 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n;
vector<double>psa,psb,alla,allb;

void vorod(){
	cin>>n;
	alla.resize(n);
	allb.resize(n);
	for(int i=0;i<n;i++){
		cin>>alla[i]>>allb[i];
	}
}

void pre(){
	sort(allb.rbegin(),allb.rend());
	sort(alla.rbegin(),alla.rend());
	psa.resize(n);
	psb.resize(n);
	psa[0]=alla[0];
	psb[0]=allb[0];
	for(int i=1;i<n;i++){
		psa[i]=psa[i-1]+alla[i];
		psb[i]=psb[i-1]+allb[i];
	}
}

void solve(){
	double res=0;
	for(int i=1;i<=n*2;i++){
		double low=0,high=1000*i+1,mid;
		for(int j=0;j<50;j++){
			mid=(high+low)/2;
			mid+=i;
			int pa=lower_bound(psa.begin(),psa.end(),mid)-psa.begin();
			int pb=lower_bound(psb.begin(),psb.end(),mid)-psb.begin();
			if(pa==(int)psa.size()||pb==(int)psb.size()){
				high=mid-i;
				continue;
			}
			if(pa+pb+2<=i){
				low=mid-i;
				continue;
			}
			high=mid-i;
		}
		res=max(res,low);
	}
	cout<<setprecision(4)<<fixed<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...