oj.uz

Submission #782296

# Submission time Handle Problem Language Result Execution time Memory
782296 2023-07-13T19:04:56 Z TeaTime Self Study (JOI22_ho_t2) C++17
0 / 100
 543 ms 11608 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]);
        }
    }

    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 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 0 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 309 ms 11588 KB Output is correct
12 Correct 307 ms 11608 KB Output is correct
13 Correct 319 ms 11544 KB Output is correct
14 Incorrect 543 ms 11604 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 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 158 ms 6060 KB Output is correct
10 Correct 97 ms 3780 KB Output is correct
11 Correct 76 ms 3228 KB Output is correct
12 Correct 56 ms 2364 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 0 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 309 ms 11588 KB Output is correct
12 Correct 307 ms 11608 KB Output is correct
13 Correct 319 ms 11544 KB Output is correct
14 Incorrect 543 ms 11604 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 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 158 ms 6060 KB Output is correct
10 Correct 97 ms 3780 KB Output is correct
11 Correct 76 ms 3228 KB Output is correct
12 Correct 56 ms 2364 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 0 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 309 ms 11588 KB Output is correct
12 Correct 307 ms 11608 KB Output is correct
13 Correct 319 ms 11544 KB Output is correct
14 Incorrect 543 ms 11604 KB Output isn't correct
15 Halted 0 ms 0 KB -