Submission #1345819

#TimeUsernameProblemLanguageResultExecution timeMemory
1345819tte0Sure Bet (CEOI17_sure)C++20
100 / 100
59 ms2748 KiB
// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h> 
#define int int64_t
using namespace std;
///////////////////////////////////////////////////////////
int n;
vector<double> a,b;

signed main(void){
	cin>>n;
	a.resize(n);
	b.resize(n);
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];

	sort(a.rbegin(),a.rend());
	sort(b.rbegin(),b.rend());

	for(int i=1;i<n;i++)a[i]+=a[i-1];
	for(int i=1;i<n;i++)b[i]+=b[i-1];

	a.insert(a.begin(),0);
	b.insert(b.begin(),0);

	// cerr<<fixed<<setprecision(4);
	// cerr<<"a:";for(auto i:a)cerr<<" "<<i;cerr<<endl;
	// cerr<<"b:";for(auto i:b)cerr<<" "<<i;cerr<<endl;

	double ans=0;
	int pa=0,pb=0;
	while(pa<n && pb<n){
		ans=max(ans,min(a[pa],b[pb])-pa-pb);
		if(a[pa]<=b[pb])pa++;
		else pb++;
	}
	while(pa<n){
		ans=max(ans,min(a[pa],b[pb])-pa-pb);
		pa++;
	}
	while(pb<n){
		ans=max(ans,min(a[pa],b[pb])-pa-pb);
		pb++;
	}
	ans=max(ans,min(a[pa],b[pb])-pa-pb);
	cout<<fixed<<setprecision(4)<<ans<<endl;
}

/*
 * min(a[i],b[j])-i-j
 *
 * insert(x)
 * add(x)
 * max()
 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...