oj.uz

Submission #957373

# Submission time Handle Problem Language Result Execution time Memory
957373 2024-04-03T15:07:30 Z _callmelucian Sure Bet (CEOI17_sure) C++14
100 / 100
 425 ms 3668 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const ll mul = 1e9;
const ll M = 1e18;

ll a[mn], b[mn], pre_a[mn], pre_b[mn];
int n;

bool ok (ll lb) {
    // check if there exist an answer >= lb
    for (int k = 0; k <= 2 * n; k++) {
        if (pre_a[min(n, k)] < lb + 1LL * k * mul) continue;
        int best = min(n, k);
        for (int b = min(n, k); b >= 1; b /= 2) {
            while (best - b >= 0 && pre_a[best - b] >= lb + 1LL * k * mul) best -= b;
        }
        if (pre_b[min(n, k - best)] >= lb + 1LL * k * mul) return 1;
    }
    return 0;
}

ll bs (ll L, ll R) {
    if (L == R) return L;
    ll mid = (L + R) >> 1;
    if (ok(mid + 1)) return bs(mid + 1, R);
    return bs(L, mid);
}

bool compare (ld a, ld b) { return a > b; }

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        ld u, v; cin >> u >> v;
        a[i] = ll(u * mul), b[i] = (v * mul);
        //cout << a[i] << " " << b[i] << "\n";
    }
    sort(a + 1, a + 1 + n, compare);
    sort(b + 1, b + 1 + n, compare);

    for (int i = 1; i <= n; i++) {
        pre_a[i] = pre_a[i - 1] + a[i];
        pre_b[i] = pre_b[i - 1] + b[i];
    }

    cout << fixed << setprecision(4) << (ld)bs(0, M) / ld(mul) << "\n";

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2392 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2396 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 325 ms 3540 KB Output is correct
18 Correct 375 ms 3412 KB Output is correct
19 Correct 408 ms 3668 KB Output is correct
20 Correct 318 ms 3408 KB Output is correct
21 Correct 299 ms 3664 KB Output is correct
22 Correct 331 ms 3356 KB Output is correct
23 Correct 325 ms 3412 KB Output is correct
24 Correct 425 ms 3580 KB Output is correct
25 Correct 314 ms 3668 KB Output is correct
26 Correct 290 ms 3396 KB Output is correct