Submission #184010

#	Time	Username	Problem	Language	Result	Execution time	Memory
184010		Andrei_Cotor	Sure Bet (CEOI17_sure)	C++14	100 / 100	125 ms	4472 KiB

sure

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

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