Submission #898436

#	Time	Username	Problem	Language	Result	Execution time	Memory
898436		maxFedorchuk	Sure Bet (CEOI17_sure)	C++17	100 / 100	100 ms	5316 KiB

sure

#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;
}

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