Submission #1221496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221496		MrAndria	Sure Bet (CEOI17_sure)	C++20	0 / 100	0 ms	324 KiB

sure

#include <bits/stdc++.h>
using namespace std;
#define ff first;
#define ss second
#define pb push_back
#define int long long
long long n,l,r,a[100005],b[100005],ans;
long double sum;
long long pref[100005][3];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        double x,y;
        cin>>x>>y;
        a[i]=10000*x;
        b[i]=10000*y;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    reverse(a+1,a+n+1);
    reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        pref[i][0]=pref[i-1][0]+a[i];
        pref[i][1]=pref[i-1][1]+b[i];
    }
    for(int i=1;i<=n;i++){
        int tl=0;
        int tr=1e12;
        ans=0;
        while(tl<=tr){
            int k=(tl+tr)/2;
            int l=0;
            int r=n;
            int ans1=n+1;
            while(l<=r){
                int mid=(l+r)/2;
                // cout<<pref[mid][0]<<" "<<i+k<<endl;
                if(pref[mid][0]>=i*10000+k){
                    ans1=mid;
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            l=0;
            r=n;
            int ans2=n+1;
            while(l<=r){
                int mid=(l+r)/2;
                if(pref[mid][1]>=i*10000+k){
                    ans2=mid;
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            if(i>=ans2+ans1){
                ans=k;
                tl=k+1;
            }else{
                tr=k-1;
            }
        }
        // cout<<ans<<endl;
        // cout<<i<<" "<<ans<<endl;
        long double x=ans;
        sum=max(sum,x);


    }
    sum/=10000;
    cout<<fixed<<setprecision(4)<<sum<<endl;
    // cout<<sum<<endl;

}

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