oj.uz

Submission #526481

# Submission time Handle Problem Language Result Execution time Memory
526481 2022-02-15T01:21:53 Z PurpleCrayon Self Study (JOI22_ho_t2) C++17
0 / 100
 464 ms 9444 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 2e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

void solve() {
    // a[i] := max(a[i], b[i])
    // binary search, take the minimum number of a's such that I'm satisfied

    int n; ll m; cin >> n >> m;
    vector<ll> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    for (int i = 0; i < n; i++) a[i] = max(a[i], b[i]);

    auto v = [&](ll x) -> bool {
        ll has = 0;
        for (int i = 0; i < n; i++) {
            ll need = (x + a[i] - 1) / a[i];
            if (need <= m) has += m - need;
            else has -= (x - a[i] * m + b[i] - 1) / b[i];
        }
        return has >= 0;
    };

    ll lo = 0, hi = INF, mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (v(mid)) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }
    cout << lo << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 233 ms 9444 KB Output is correct
12 Correct 231 ms 9268 KB Output is correct
13 Correct 239 ms 6724 KB Output is correct
14 Incorrect 464 ms 8672 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 117 ms 4680 KB Output is correct
10 Correct 78 ms 2636 KB Output is correct
11 Correct 57 ms 2156 KB Output is correct
12 Correct 49 ms 1856 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 224 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 9 ms 392 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 233 ms 9444 KB Output is correct
12 Correct 231 ms 9268 KB Output is correct
13 Correct 239 ms 6724 KB Output is correct
14 Incorrect 464 ms 8672 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 117 ms 4680 KB Output is correct
10 Correct 78 ms 2636 KB Output is correct
11 Correct 57 ms 2156 KB Output is correct
12 Correct 49 ms 1856 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 224 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 9 ms 392 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 233 ms 9444 KB Output is correct
12 Correct 231 ms 9268 KB Output is correct
13 Correct 239 ms 6724 KB Output is correct
14 Incorrect 464 ms 8672 KB Output isn't correct
15 Halted 0 ms 0 KB -