oj.uz

Submission #782301

# Submission time Handle Problem Language Result Execution time Memory
782301 2023-07-13T19:09:38 Z TeaTime Self Study (JOI22_ho_t2) C++17
0 / 100
 524 ms 11712 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 200'100, LG = 18, INF = 1'000'000'000'000'000'100;

ll n, m;
vector<ll> vec1, vec2;

bool check(ll val) {
    vector<ll> vec;
    ll left = 0;
    for (int i = 0; i < n; i++) {
        ll needed = (val - 1) / vec1[i] + 1;

        if (needed <= m) {
            left += m - needed;
            vec.push_back(0);
        } else {
            vec.push_back(val - m * vec1[i]);
        }

        left = min(left, INF);
    }

    for (int i = 0; i < n; i++) {
        if (vec[i] == 0) continue;

        left -= (vec[i] - 1) / vec2[i] + 1;
    }

    return left >= 0;
}

int main() {
    fastInp;

    cin >> n >> m;
    vec1.resize(n);
    vec2.resize(n);
    for (auto &c : vec1) cin >> c;
    for (auto &c : vec2) cin >> c;

    for (int i = 0; i < n; i++) {
        vec1[i] = max(vec1[i], vec2[i]);
    }

    ll l = 0, r = INF;

    while (r - l > 1) {
        ll mid = (l + r) / 2;

        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << l;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 318 ms 11712 KB Output is correct
12 Correct 305 ms 11564 KB Output is correct
13 Correct 336 ms 11572 KB Output is correct
14 Incorrect 524 ms 11528 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 167 ms 6012 KB Output is correct
10 Correct 97 ms 3788 KB Output is correct
11 Correct 76 ms 3572 KB Output is correct
12 Correct 56 ms 2432 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 8 ms 468 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 318 ms 11712 KB Output is correct
12 Correct 305 ms 11564 KB Output is correct
13 Correct 336 ms 11572 KB Output is correct
14 Incorrect 524 ms 11528 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 167 ms 6012 KB Output is correct
10 Correct 97 ms 3788 KB Output is correct
11 Correct 76 ms 3572 KB Output is correct
12 Correct 56 ms 2432 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 8 ms 468 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 318 ms 11712 KB Output is correct
12 Correct 305 ms 11564 KB Output is correct
13 Correct 336 ms 11572 KB Output is correct
14 Incorrect 524 ms 11528 KB Output isn't correct
15 Halted 0 ms 0 KB -