Submission #528774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528774	2022-02-21T11:33:40 Z	FireGhost1301	Self Study (JOI22_ho_t2)	C++11	0 / 100	468 ms	2728 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, 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	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 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	1 ms	204 KB	Output is correct
10	Correct	4 ms	364 KB	Output is correct
11	Correct	233 ms	2728 KB	Output is correct
12	Correct	240 ms	2628 KB	Output is correct
13	Correct	232 ms	2628 KB	Output is correct
14	Incorrect	468 ms	2644 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	0 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	0 ms	204 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	1484 KB	Output is correct
10	Correct	90 ms	1100 KB	Output is correct
11	Correct	72 ms	892 KB	Output is correct
12	Correct	51 ms	772 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 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	1 ms	204 KB	Output is correct
10	Correct	4 ms	364 KB	Output is correct
11	Correct	233 ms	2728 KB	Output is correct
12	Correct	240 ms	2628 KB	Output is correct
13	Correct	232 ms	2628 KB	Output is correct
14	Incorrect	468 ms	2644 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	0 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	0 ms	204 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	1484 KB	Output is correct
10	Correct	90 ms	1100 KB	Output is correct
11	Correct	72 ms	892 KB	Output is correct
12	Correct	51 ms	772 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 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	1 ms	204 KB	Output is correct
10	Correct	4 ms	364 KB	Output is correct
11	Correct	233 ms	2728 KB	Output is correct
12	Correct	240 ms	2628 KB	Output is correct
13	Correct	232 ms	2628 KB	Output is correct
14	Incorrect	468 ms	2644 KB	Output isn't correct
15	Halted	0 ms	0 KB	-