Submission #593559

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593559	2022-07-11T11:52:59 Z	piOOE	Self Study (JOI22_ho_t2)	C++17	0 / 100	515 ms	5392 KB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    const ll inf = 3e18;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    ll L = 0, R = inf;
    while (L + 1 < R) {
        ll mid = (L + R) >> 1;
        auto check = [&]() -> bool {
            ll cnt = n * (ll)m;
            for (int i = 0; i < n; ++i) {
                if (b[i] >= a[i]) {
                    ll now = (mid + b[i] - 1) / b[i];
                    cnt -= now;
                } else {
                    ll now = (mid + a[i] - 1) / a[i];
                    if (now <= m) {
                        cnt -= now;
                    } else {
                        ll whole = m + (mid - a[i] * m + b[i] - 1) / b[i];
                        cnt -= whole;
                    }
                }
            }
            return cnt >= 0;
        };
        if (check()) {
            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	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	316 KB	Output is correct
9	Correct	1 ms	252 KB	Output is correct
10	Correct	5 ms	480 KB	Output is correct
11	Correct	208 ms	5388 KB	Output is correct
12	Correct	231 ms	5392 KB	Output is correct
13	Correct	173 ms	5332 KB	Output is correct
14	Incorrect	515 ms	5332 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	316 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	98 ms	3040 KB	Output is correct
10	Correct	64 ms	2280 KB	Output is correct
11	Correct	46 ms	1868 KB	Output is correct
12	Correct	35 ms	1620 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	1 ms	212 KB	Output is correct
18	Incorrect	7 ms	460 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	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	316 KB	Output is correct
9	Correct	1 ms	252 KB	Output is correct
10	Correct	5 ms	480 KB	Output is correct
11	Correct	208 ms	5388 KB	Output is correct
12	Correct	231 ms	5392 KB	Output is correct
13	Correct	173 ms	5332 KB	Output is correct
14	Incorrect	515 ms	5332 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	316 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	98 ms	3040 KB	Output is correct
10	Correct	64 ms	2280 KB	Output is correct
11	Correct	46 ms	1868 KB	Output is correct
12	Correct	35 ms	1620 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	1 ms	212 KB	Output is correct
18	Incorrect	7 ms	460 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	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	316 KB	Output is correct
9	Correct	1 ms	252 KB	Output is correct
10	Correct	5 ms	480 KB	Output is correct
11	Correct	208 ms	5388 KB	Output is correct
12	Correct	231 ms	5392 KB	Output is correct
13	Correct	173 ms	5332 KB	Output is correct
14	Incorrect	515 ms	5332 KB	Output isn't correct
15	Halted	0 ms	0 KB	-