Submission #810984

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810984	2023-08-06T18:54:47 Z	tkwiatkowski	Self Study (JOI22_ho_t2)	C++17	0 / 100	427 ms	8416 KB

Main

#include <iostream>
#include <vector>
using namespace std;

bool check(long long min_lvl, int m, vector<int> &A, vector<int> &B) {
    long long cnt = 0;
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        int a = max(A[i], B[i]);
        int b = B[i];
        long long curr_cnt = min((long long)m, (min_lvl + a - 1) / a);
        cnt += curr_cnt + max((long long)0, (min_lvl - curr_cnt * a + b - 1) / b);
    }
    return cnt <= (long long)n * m;
}

long long BS(int m, vector<int> &A, vector<int> &B) {
    long long lo = 0, hi = 1e18;
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        if (check(mid, m, A, B))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<int> A(n), B(n);
    for (auto &a : A)
        cin >> a;
    for (auto &b : B)
        cin >> b;

    cout << BS(m, A, B) << '\n';
    return 0;
}

Subtask #1

0 / 10.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	1 ms	320 KB	Output is correct
7	Correct	0 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	340 KB	Output is correct
11	Correct	240 ms	8416 KB	Output is correct
12	Correct	243 ms	8408 KB	Output is correct
13	Correct	232 ms	6484 KB	Output is correct
14	Incorrect	427 ms	6480 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	1 ms	316 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	122 ms	4392 KB	Output is correct
10	Correct	81 ms	3024 KB	Output is correct
11	Correct	61 ms	2360 KB	Output is correct
12	Correct	49 ms	1944 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	316 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	8 ms	332 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	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	1 ms	320 KB	Output is correct
7	Correct	0 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	340 KB	Output is correct
11	Correct	240 ms	8416 KB	Output is correct
12	Correct	243 ms	8408 KB	Output is correct
13	Correct	232 ms	6484 KB	Output is correct
14	Incorrect	427 ms	6480 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	1 ms	316 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	122 ms	4392 KB	Output is correct
10	Correct	81 ms	3024 KB	Output is correct
11	Correct	61 ms	2360 KB	Output is correct
12	Correct	49 ms	1944 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	316 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	8 ms	332 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	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	1 ms	320 KB	Output is correct
7	Correct	0 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	340 KB	Output is correct
11	Correct	240 ms	8416 KB	Output is correct
12	Correct	243 ms	8408 KB	Output is correct
13	Correct	232 ms	6484 KB	Output is correct
14	Incorrect	427 ms	6480 KB	Output isn't correct
15	Halted	0 ms	0 KB	-