Submission #528775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528775	2022-02-21T11:35:14 Z	FireGhost1301	Self Study (JOI22_ho_t2)	C++11	0 / 100	471 ms	2648 KB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 3;
int n, m, a[N], b[N];

bool check(long long d) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        long long x = d;
        long long k = (x + a[i] - 1) / a[i];
        k = min(k, (long long)m);
        x -= k * a[i];
        sum += k;
        if (x > 0) sum += (x + b[i] - 1) / b[i];
    }
    return sum <= 1LL * n * m;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i], a[i] = max(a[i], b[i]);
    long long l = 1, r = 1e18 + 7, ans = 0, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1

0 / 10.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	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	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	221 ms	2640 KB	Output is correct
12	Correct	239 ms	2640 KB	Output is correct
13	Correct	232 ms	2644 KB	Output is correct
14	Incorrect	471 ms	2648 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	1 ms	216 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	117 ms	1412 KB	Output is correct
10	Correct	78 ms	1100 KB	Output is correct
11	Correct	61 ms	896 KB	Output is correct
12	Correct	47 ms	780 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Incorrect	9 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	1 ms	204 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	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	221 ms	2640 KB	Output is correct
12	Correct	239 ms	2640 KB	Output is correct
13	Correct	232 ms	2644 KB	Output is correct
14	Incorrect	471 ms	2648 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	1 ms	216 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	117 ms	1412 KB	Output is correct
10	Correct	78 ms	1100 KB	Output is correct
11	Correct	61 ms	896 KB	Output is correct
12	Correct	47 ms	780 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Incorrect	9 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	1 ms	204 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	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	221 ms	2640 KB	Output is correct
12	Correct	239 ms	2640 KB	Output is correct
13	Correct	232 ms	2644 KB	Output is correct
14	Incorrect	471 ms	2648 KB	Output isn't correct
15	Halted	0 ms	0 KB	-