Submission #969200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969200	2024-04-24T16:26:34 Z	yellowtoad	Self Study (JOI22_ho_t2)	C++17	10 / 100	213 ms	11344 KB

Main

#include <iostream>
#include <algorithm>
#define f first
#define s second
using namespace std;

long long n, m, a[300010], b[300010], l = 0, r = 2e9, mid, cnt, req;

bool check() {
	cnt = req = 0;
	for (int i = 1; i <= n; i++) {
		if (b[i] > a[i]) {
			cnt += m;
			req += (mid+b[i]-1)/b[i];
		} else {
			if (a[i]*m >= mid) cnt += (a[i]*m-mid)/a[i];
			else req += (mid-a[i]*m+b[i]-1)/b[i];
		}
	}
	if (cnt < req) return 0;
	else return 1;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	while (l <= r) {
		mid = (l+r)/2;
		if (!check()) r = mid-1;
		else l = mid+1;
	}
	cout << r << endl;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 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	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	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	207 ms	5032 KB	Output is correct
12	Correct	202 ms	5104 KB	Output is correct
13	Correct	155 ms	5108 KB	Output is correct
14	Correct	177 ms	5024 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	139 ms	6176 KB	Output is correct
17	Correct	213 ms	11344 KB	Output is correct
18	Correct	200 ms	10920 KB	Output is correct

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	139 ms	6176 KB	Output is correct
3	Correct	213 ms	11344 KB	Output is correct
4	Correct	200 ms	10920 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	Incorrect	1 ms	2396 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 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	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	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	207 ms	5032 KB	Output is correct
12	Correct	202 ms	5104 KB	Output is correct
13	Correct	155 ms	5108 KB	Output is correct
14	Correct	177 ms	5024 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	1 ms	2396 KB	Output isn't correct
19	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	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Incorrect	1 ms	2396 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 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	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	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	207 ms	5032 KB	Output is correct
12	Correct	202 ms	5104 KB	Output is correct
13	Correct	155 ms	5108 KB	Output is correct
14	Correct	177 ms	5024 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	1 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-