oj.uz

Submission #938324

# Submission time Handle Problem Language Result Execution time Memory
938324 2024-03-05T04:39:58 Z vjudge1 Sure Bet (CEOI17_sure) C++17
100 / 100
 146 ms 8104 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

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

    int n; cin >> n;
    using ld = long double;
    vector <ld> a, b;
    for ( int i = 0; i < n; i++ ){
        ld x, y; cin >> x >> y;
        a.pb(x), b.pb(y);
    }
    sort(all(a), greater <ld> ());
    sort(all(b), greater <ld> ());
    n = a.size();
    int m = b.size();
    vector <ld> pf(m + 1), mx(m + 1);
    for ( int i = 0; i < m; i++ ){
        pf[i + 1] = pf[i] + b[i];
        mx[i + 1] = max(mx[i], pf[i + 1] - (i + 1));
    }
    auto ok = [&](ld x){
        ld s = 0;
        for ( int i = 0; i <= n; i++ ){
            if ( s - i >= x ){
                int j = max(0LL, (int)floor(s - x - i));
                chmin(j, m);
                if ( mx[j] - i >= x ){
                    return true;
                }
            }
            if ( i < n ){
                s += a[i];
            }
        } return false;
    };
    ld l = 0, r = 1e12;
    for ( int _ = 0; _ <= 100; _++ ){
        ld md = (l + r) / 2;
        if ( ok(md) ) l = md;
        else r = md;
    }
    cout << fixed << setprecision(4) << l;

    cout << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 142 ms 6828 KB Output is correct
18 Correct 146 ms 7848 KB Output is correct
19 Correct 138 ms 7732 KB Output is correct
20 Correct 146 ms 7968 KB Output is correct
21 Correct 97 ms 7848 KB Output is correct
22 Correct 145 ms 7856 KB Output is correct
23 Correct 144 ms 7856 KB Output is correct
24 Correct 141 ms 8104 KB Output is correct
25 Correct 143 ms 7860 KB Output is correct
26 Correct 97 ms 7904 KB Output is correct