oj.uz

Submission #884641

# Submission time Handle Problem Language Result Execution time Memory
884641 2023-12-07T20:56:52 Z EJIC_B_KEDAX Self Study (JOI22_ho_t2) C++14
0 / 100
 442 ms 10932 KB 
#ifdef LOCAL
    //#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(418);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#else
    freopen("input.txt", "r", stdin);
#endif
    // srand(time(0));
    init();
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    ll l = 0, r = 2e18;
    while (r - l > 1) {
        ll mid = (r + l) / 2;
        ll free = (ll)m * n;
        vector<ll> skill(n, 0);
        for (int i = 0; i < n; i++) {
            if (a[i] > b[i]) {
                ll have = (mid + a[i] - 1) / a[i];
                have = min(have, (ll)m);
                skill[i] += a[i] * have;
                free -= have;
            }
        }
        for (int i = 0; i < n; i++) {
            ll need = mid - skill[i];
            if (need > 0) {
                ll have = (need + b[i] - 1) / b[i];
                skill[i] += b[i] * have;
                free -= have;
            }
        }
        if (free >= 0) {
            l = mid;
        } else {
            r = mid;
        }
        // cout << "!!! " << r << ' ' << l << '\n';
    }
    cout << l << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 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 464 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 240 ms 10836 KB Output is correct
12 Correct 242 ms 10932 KB Output is correct
13 Correct 163 ms 8788 KB Output is correct
14 Incorrect 442 ms 9000 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 86 ms 5572 KB Output is correct
10 Correct 54 ms 3940 KB Output is correct
11 Correct 41 ms 3084 KB Output is correct
12 Correct 35 ms 2508 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Incorrect 5 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 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 464 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 240 ms 10836 KB Output is correct
12 Correct 242 ms 10932 KB Output is correct
13 Correct 163 ms 8788 KB Output is correct
14 Incorrect 442 ms 9000 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 86 ms 5572 KB Output is correct
10 Correct 54 ms 3940 KB Output is correct
11 Correct 41 ms 3084 KB Output is correct
12 Correct 35 ms 2508 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Incorrect 5 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 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 464 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 240 ms 10836 KB Output is correct
12 Correct 242 ms 10932 KB Output is correct
13 Correct 163 ms 8788 KB Output is correct
14 Incorrect 442 ms 9000 KB Output isn't correct
15 Halted 0 ms 0 KB -