제출 #898436

#제출 시각아이디문제언어결과실행 시간메모리
898436maxFedorchukSure Bet (CEOI17_sure)C++17
100 / 100
100 ms5316 KiB
#include <bits/stdc++.h>
using namespace std;

const long double eps=1e-5;
const long long INF=1e18;

const long long MX=1e5+10;

long double a[MX],b[MX];

long long n;

bool pos(long double zn)
{
    for(long long i=1;i<=n;i++)
    {
        if(a[i]<zn)
        {
            continue;
        }

        long long in=(a[i]-zn);
        in=min(in,n);

        if((b[in]-i)>=zn)
        {
            return 1;
        }
    }

    return 0;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n;

    for(long long i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        a[i]--;
        b[i]--;
    }

    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);

    sort(b+1,b+1+n);
    reverse(b+1,b+1+n);

    for(long long i=2;i<=n;i++)
    {
        a[i]+=a[i-1];
        b[i]+=b[i-1];
    }

    long double l=0,r=INF;

    while((l+eps)<r)
    {
        long double mid=(l+r)/2;

        if(pos(mid))
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }

    cout<<fixed<<setprecision(4)<<l<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...