Submission #997805

#	Time	Username	Problem	Language	Result	Execution time	Memory
997805		amirhoseinfar1385	Sure Bet (CEOI17_sure)	C++17	100 / 100	1208 ms	6724 KiB

sure

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n;
vector<long 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(){
	long double res=0;
	for(int i=1;i<=n*2;i++){
		long 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();
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40