제출 #1205563

#제출 시각아이디문제언어결과실행 시간메모리
1205563yassiaSure Bet (CEOI17_sure)C++20
20 / 100
0 ms328 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);

void solve1() {
    ll n;
    cin>> n;
    vector<ll> a(n);
    vector<ll> b(n);
    ll sum1 = 0;
    ll sum2 = 0;
    for (int i = 0; i < n; ++i){
        ld ai, bi;
        cin >> ai >> bi;
        ll x = ai*100000ll;
        ll y = bi*100000ll;
        a[i] = x;
        b[i] = y;
        sum1+=a[i];
        sum2+=b[i];
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    ll l = 0;
    ll r = sum1+sum2+1;
    while (r-l>1) {
        ll mi = (l+r)/2;
        ll A = 0;
        ll B = 0;
        ll i1 = 0;
        ll i2 = 0;
        bool change = true;
        while (change) {
            change= false;
            if (A < mi && i1<n){
                A += (a[i1]-100000);
                B -= 100000;
                i1++;
                change = true;
            }
            if (B < mi && i2 < n){
                B += (b[i2]-100000);
                A -= 100000;
                i2++;
                change = true;
            }
        }
        if (B >= mi && A >= mi){
            l = mi;
        }
        else {
            r = mi;
        }
    }
    cout<<(ld)l/((ld)100000);

}

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...