Submission #1205568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205568		yassia	Sure Bet (CEOI17_sure)	C++20	60 / 100	43 ms	1860 KiB

sure

#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 = 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*1000000ll;
        ll y = bi*1000000ll;
        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+2;
    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]-1000000);
                B -= 1000000;
                i1++;
                change = true;
            }
            if (B < mi && i2 < n){
                B += (b[i2]-1000000);
                A -= 1000000;
                i2++;
                change = true;
            }
        }
        if (B >= mi && A >= mi){
            l = mi;
        }
        else {
            r = mi;
        }
    }
    cout<<(long double)l/((long double)1000000);

}

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();
}

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