Submission #886561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886561	2023-12-12T10:22:30 Z	dubabuba	Self Study (JOI22_ho_t2)	C++14	0 / 100	364 ms	15596 KB

Main

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

#define int long long
typedef long long ll;
const int mxn = 3e5 + 10;
const int mxm = 1e9 + 10;
ll a[mxn], b[mxn], x[mxn];
int n, m, id[mxn];

void build() {
	for(int i = 0; i < n; i++) {
		a[i] = max(a[i], b[i]);
		x[i] = a[i] * m;
		id[i] = i;
	}

	sort(id, id + n, [&](int i, int j) {
		return x[i] < x[j];
	});
}

ll sus(ll s, ll a) {
	return (s + a - 1) / a;
}

bool can(ll MID) {
	ll MIN = 0, MAX = 0;
	for(int t = 0; t < n; t++) {
		int i = id[t];

		if(x[i] < MID) MIN += (MID - x[i] + b[i] - 1) / b[i];
		if(x[i] > MID) MAX += (x[i] - MID) / a[i];
	}
	return MIN <= MAX;
}

signed main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int j = 0; j < n; j++)
		cin >> b[j];

	build();

	ll L = 0, R = 1e18 + 10;
	while(R - L > 1) {
		ll M = L + (R - L) / 2;
		if(can(M)) L = M;
		else R = M;
	}

	cout << L << '\n';
	return 0;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6488 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6584 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	5 ms	6492 KB	Output is correct
11	Correct	317 ms	15392 KB	Output is correct
12	Correct	334 ms	15596 KB	Output is correct
13	Correct	216 ms	13400 KB	Output is correct
14	Incorrect	364 ms	13616 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	6492 KB	Output is correct
2	Correct	1 ms	6500 KB	Output is correct
3	Correct	1 ms	6500 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6496 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6496 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	140 ms	11684 KB	Output is correct
10	Correct	94 ms	10580 KB	Output is correct
11	Correct	85 ms	10064 KB	Output is correct
12	Correct	57 ms	9812 KB	Output is correct
13	Correct	2 ms	6488 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	1 ms	6492 KB	Output is correct
18	Incorrect	6 ms	6488 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	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6488 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6584 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	5 ms	6492 KB	Output is correct
11	Correct	317 ms	15392 KB	Output is correct
12	Correct	334 ms	15596 KB	Output is correct
13	Correct	216 ms	13400 KB	Output is correct
14	Incorrect	364 ms	13616 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	6492 KB	Output is correct
2	Correct	1 ms	6500 KB	Output is correct
3	Correct	1 ms	6500 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6496 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6496 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	140 ms	11684 KB	Output is correct
10	Correct	94 ms	10580 KB	Output is correct
11	Correct	85 ms	10064 KB	Output is correct
12	Correct	57 ms	9812 KB	Output is correct
13	Correct	2 ms	6488 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	1 ms	6492 KB	Output is correct
18	Incorrect	6 ms	6488 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	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6488 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6584 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	5 ms	6492 KB	Output is correct
11	Correct	317 ms	15392 KB	Output is correct
12	Correct	334 ms	15596 KB	Output is correct
13	Correct	216 ms	13400 KB	Output is correct
14	Incorrect	364 ms	13616 KB	Output isn't correct
15	Halted	0 ms	0 KB	-