Submission #184010

#TimeUsernameProblemLanguageResultExecution timeMemory
184010Andrei_CotorSure Bet (CEOI17_sure)C++14
100 / 100
125 ms4472 KiB
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

double A[100005],B[100005],SumB[100005];

bool cmp(double a, double b)
{
    return a>b;
}

double src(double winA, double winB, int n)
{
    int poz=0;
    for(int i=16; i>=0; i--)
    {
        if(poz+(1<<i)<=n && (winA-1.0*(poz+(1<<i)))>(winB+SumB[poz+(1<<i)]))
            poz+=(1<<i);
    }

    double rez=min(winA-1.0*poz,winB+SumB[poz]);
    if(poz<n)
        rez=max(rez,min(winA-1.0*poz-1.0,winB+SumB[poz+1]));
    return rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>A[i]>>B[i];
        A[i]-=1.0;
        B[i]-=1.0;
    }

    sort(A+1,A+n+1,cmp);
    sort(B+1,B+n+1,cmp);

    for(int i=1; i<=n; i++)
        SumB[i]=SumB[i-1]+B[i];

    double winA=0.0;
    double winB=0.0;
    double rez=0.0;
    for(int i=0; i<=n; i++)
    {
        rez=max(rez,src(winA,winB,n));
        winA+=A[i+1];
        winB-=1.0;
    }

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