Submission #1219369

#TimeUsernameProblemLanguageResultExecution timeMemory
1219369boclobanchatSure Bet (CEOI17_sure)C++20
100 / 100
49 ms1864 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
double pref[2][MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=0;j<2;j++) cin>>pref[j][i];
    sort(pref[0]+1,pref[0]+n+1,greater<double>());
    sort(pref[1]+1,pref[1]+n+1,greater<double>());
    for(int i=1;i<=n;i++) pref[0][i]+=pref[0][i-1],pref[1][i]+=pref[1][i-1];
    double ans=0;
    for(int i=1;i<=n*2;i++)
    {
    	int l=max(0,i-n),r=min(n,i),pos=l;
    	double mx=0;
    	while(l<=r)
    	{
    		int mid=(l+r)/2;
    		if(pref[0][mid]<pref[1][i-mid]) l=mid+1,pos=mid;
    		else r=mid-1;
		}
		mx=max(mx,min(pref[0][pos],pref[1][i-pos]));
		if(i-pos&&pos<n) mx=max(mx,min(pref[0][pos+1],pref[1][i-pos-1]));
		ans=max(ans,mx-i);
//		cout<<mx<<" "<<i<<"\n";
	}
	cout<<setprecision(4)<<fixed<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...