Submission #1205575

#TimeUsernameProblemLanguageResultExecution timeMemory
1205575yassiaSure Bet (CEOI17_sure)C++20
100 / 100
69 ms3472 KiB
#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

using str = string;
using ld = long double;

auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
ld eps = 1e-5;
void solve1() {
    ll n;
    cin>> n;
    vector<ld> a(n);
    vector<ld> b(n);
    ld sum1 = 0;
    ld sum2 = 0;
    for (int i = 0; i < n; ++i){
        ld ai, bi;
        cin >> ai >> bi;
        a[i] = ai;
        b[i] = bi;
        sum1+=a[i];
        sum2+=b[i];
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    ld l = 0;
    ld r = sum1+sum2+2;
    while (r-l>eps) {
        ld mi = (l+r)/2;
        ld A = 0;
        ld B = 0;
        ll i1 = 0;
        ll i2 = 0;
        bool change = true;
        while (change) {
            change= false;
            if (A < mi && i1<n){
                A += (a[i1]-1);
                B -= 1;
                i1++;
                change = true;
            }
            if (B < mi && i2 < n){
                B += (b[i2]-1);
                A -= 1;
                i2++;
                change = true;
            }
        }
        if (B >= mi && A >= mi){
            l = mi;
        }
        else {
            r = mi;
        }
    }
    cout<< l<<endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cout<<fixed<<setprecision(4);
    int t1=1;
    while (t1) t1--, solve1();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...