Submission #936131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
936131	2024-03-01T08:02:42 Z	weakweakweak	Self Study (JOI22_ho_t2)	C++14	0 / 100	390 ms	11004 KB

Main

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

#define ll long long
ll n, m, a[310000], b[310000];

bool can (ll v) {
    ll now = 0;
    for (int i = 1; i <= n; i++) {
        ll inclass = (v + a[i] - 1) / a[i];
        if (inclass == m) continue;
        if (inclass < m) now += m - inclass;
        else {
            ll z = v - m * a[i];
            now -= (z + b[i] - 1) / b[i];
        }
    }
return now >= 0;}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    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]);
    }

    ll l = 1, r = 1e17;
    while (l + 2 < r) {
        ll mid = (l + r) / 2;
        if (can(mid)) l = mid;
        else r = mid;
    }
    while (can(l + 1) and l < r) l++;
    // cout << can(19) << '\n';
    cout << l << '\n'; 
return 0;}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2636 KB	Output is correct
11	Correct	191 ms	10832 KB	Output is correct
12	Correct	188 ms	11004 KB	Output is correct
13	Correct	191 ms	8784 KB	Output is correct
14	Incorrect	390 ms	8892 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	101 ms	7628 KB	Output is correct
10	Correct	65 ms	6660 KB	Output is correct
11	Correct	48 ms	5980 KB	Output is correct
12	Correct	41 ms	5724 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Incorrect	8 ms	2568 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	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2636 KB	Output is correct
11	Correct	191 ms	10832 KB	Output is correct
12	Correct	188 ms	11004 KB	Output is correct
13	Correct	191 ms	8784 KB	Output is correct
14	Incorrect	390 ms	8892 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	101 ms	7628 KB	Output is correct
10	Correct	65 ms	6660 KB	Output is correct
11	Correct	48 ms	5980 KB	Output is correct
12	Correct	41 ms	5724 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Incorrect	8 ms	2568 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	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2636 KB	Output is correct
11	Correct	191 ms	10832 KB	Output is correct
12	Correct	188 ms	11004 KB	Output is correct
13	Correct	191 ms	8784 KB	Output is correct
14	Incorrect	390 ms	8892 KB	Output isn't correct
15	Halted	0 ms	0 KB	-