Submission #46943

#	Time	Username	Problem	Language	Result	Execution time	Memory
46943		dqhungdl	Sure Bet (CEOI17_sure)	C++17	100 / 100	130 ms	16832 KiB

sure

#include <bits/stdc++.h>
using namespace std;

const double EXP=1e-6;
int T,m=0,n=0;
double a[100005],b[100005];

bool Check(double lim)
{
    for(int i=1;i<=m;i++)
    {
        int lim2=min(int(max(a[i]-lim,0.0)),n);
        if(b[lim2]-double(i)>=lim)
            return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>T;
    double x,y;
    while(T--)
    {
        cin>>x>>y;
        if(x>=1.0)
            a[++m]=x-1.0;
        if(y>=1)
            b[++n]=y-1.0;
    }
    sort(a+1,a+m+1,greater<double>());
    sort(b+1,b+n+1,greater<double>());
    for(int i=1;i<=m;i++)
        a[i]+=a[i-1];
    for(int i=1;i<=n;i++)
        b[i]+=b[i-1];
    double res,l=0,r=1e9;
    while(r-l>=EXP)
    {
        double mid=(l+r)/2.0;
        if(Check(mid)==true)
        {
            res=mid;
            l=mid+EXP;
        }
        else
            r=mid-EXP;
    }
    cout<<setprecision(4)<<fixed<<res;
}

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