oj.uz

Submission #941105

# Submission time Handle Problem Language Result Execution time Memory
941105 2024-03-08T07:14:30 Z Pring Self Study (JOI22_ho_t2) C++17
0 / 100
 451 ms 5136 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
const string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define dout(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 300005, INF = 3.9e18;
int n, m, a[MXN], b[MXN];

int DC(int a, int b) {
    if (a == 0) return 0;
    return (a - 1) / b + 1;
}

bool check(int x) {
    auto f = [&](int x, int a, int b) -> int {
        if (DC(x, a) <= m) return m - DC(x, a);
        x -= a * m;
        return -DC(x, b);
    };
    int now = 0;
    FOR(i, 0, n) {
        if (a[i] > b[i]) now += f(x, a[i], b[i]);
        else {
            now += m;
            now -= DC(x, b[i]);
        }
    }
    return (now >= 0);
}

int miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> a[i];
    FOR(i, 0, n) cin >> b[i];
    int l = 0, r = INF;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        (check(mid) ? l : r) = mid;
    }
    return l;
}

// int check() {
//     int ans = LLONG_MAX;
//     FOR(i, 0, n) ans = min(ans, max(a[i], b[i]));
//     return ans;
// }

// void PRINT() {
//     cout << n << ' ' << m << '\n';
//     FOR(i, 0, n) cout << a[i] << ' ';
//     cout << '\n';
//     FOR(i, 0, n) cout << b[i] << ' ';
//     cout << '\n';
// }

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    cout << miku() << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 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 0 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 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 188 ms 5132 KB Output is correct
12 Correct 192 ms 5132 KB Output is correct
13 Correct 137 ms 5132 KB Output is correct
14 Incorrect 451 ms 5136 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 2396 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 2392 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 75 ms 4748 KB Output is correct
10 Correct 55 ms 4700 KB Output is correct
11 Correct 38 ms 4700 KB Output is correct
12 Correct 32 ms 4700 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Incorrect 5 ms 2396 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 2396 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 0 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 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 188 ms 5132 KB Output is correct
12 Correct 192 ms 5132 KB Output is correct
13 Correct 137 ms 5132 KB Output is correct
14 Incorrect 451 ms 5136 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 2396 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 2392 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 75 ms 4748 KB Output is correct
10 Correct 55 ms 4700 KB Output is correct
11 Correct 38 ms 4700 KB Output is correct
12 Correct 32 ms 4700 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Incorrect 5 ms 2396 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 2396 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 0 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 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 188 ms 5132 KB Output is correct
12 Correct 192 ms 5132 KB Output is correct
13 Correct 137 ms 5132 KB Output is correct
14 Incorrect 451 ms 5136 KB Output isn't correct
15 Halted 0 ms 0 KB -