Submission #800094

#TimeUsernameProblemLanguageResultExecution timeMemory
800094detroiddhSure Bet (CEOI17_sure)C++17
60 / 100
96 ms5140 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 1e5 + 3 , inf = (ll)1e6;
const ll mod = 1e9 + 7;

int n;
ld eps = 1e-5;
ld a[maxn] , b[maxn];

bool ss(ld i , ld j)
{
    return i > j;
}

bool check(ld mid)
{
    int p1 = 1 , p2 = 1;
    ld so1 = 0 , so2 = 0;
    while(so1 < mid || so2 < mid)
    {
        while(so1 < mid)
        {
            if(p1 > n) return false;
            so1 += a[p1] - 1;
            so2 -= 1;
            p1++;
        }
        while(so2 < mid)
        {
            if(p2 > n) return false;
            so2 += b[p2] - 1;
            so1 -= 1;
            p2++;
        }
    }

    return true;
}

ld solve()
{
    ld lo = 0 , hi = inf , kq = 0;
    while(lo + eps <= hi)
    {
        ld mid = (lo + hi) / 2.0;
        if(check(mid))
        {
            lo = mid;
            kq = max(kq , mid);
        }
        else hi = mid;
    }

    return kq;
}

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

   cin>>n;

   for(int i = 1 ; i <= n ; ++i)
    cin>>a[i]>>b[i];

   sort(a + 1 , a + n + 1 , ss);
   sort(b + 1 , b + n + 1 , ss);

   cout<<fixed<<setprecision(4)<<solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...