Submission #1018797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1018797	2024-07-10T09:51:27 Z	vjudge1	Self Study (JOI22_ho_t2)	C++17	0 / 100	129 ms	9752 KB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;

#define int ll

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin >> n >> m;
	
	vector<int> a(n), b(n);
	
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	
	for(int i=0;i<n;i++){
		cin >> b[i];
	}
	
	auto check = [&](ll p){
		ll t = 0;
		
		for(int i=0;i<n;i++){
			if(b[i] > a[i]){
				// не выгодно идти на лекции
				ll b_ = (p + b[i] - 1) / b[i];
				// нужно b_ времени чтобы понять на как минимум p
				t += b_;
			} else {
				if(a[i] * 1ll * m >= p){
					// выгодно идти на лекции, и лекций хватает чтобы понять на р
					ll a_ = (p + a[i] - 1) / a[i];
					// нужно а_ времеи чтобы понять на как минимум р
					
					t += a_;
				} else {
					// выгодно идти на лекции, но лекция не хватает чтобы понять на р
					ll a_ = m;
					ll b_ = (p - a[i] * 1ll * a_ + b[i] - 1) / b[i];
					
					t += a_ + b_;
				}
			}
		}
		
		if(t <= n * 1ll * m) return true;
		else return false;
	};
	
	ll l = 1, r = 1e18 + 1;
	while(r - l > 1){
		ll m = (l + r) >> 1;
		
		if(check(m)) l = m;
		else r = m;
	}
	
	if(check(r)) cout<<r<<"\n";
	else cout<<l<<"\n";
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	129 ms	9532 KB	Output is correct
12	Correct	122 ms	9752 KB	Output is correct
13	Correct	74 ms	8020 KB	Output is correct
14	Incorrect	87 ms	8016 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	42 ms	5248 KB	Output is correct
10	Correct	29 ms	3932 KB	Output is correct
11	Correct	21 ms	2912 KB	Output is correct
12	Correct	18 ms	2564 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	456 KB	Output is correct
16	Correct	0 ms	612 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Incorrect	2 ms	720 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	129 ms	9532 KB	Output is correct
12	Correct	122 ms	9752 KB	Output is correct
13	Correct	74 ms	8020 KB	Output is correct
14	Incorrect	87 ms	8016 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	42 ms	5248 KB	Output is correct
10	Correct	29 ms	3932 KB	Output is correct
11	Correct	21 ms	2912 KB	Output is correct
12	Correct	18 ms	2564 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	456 KB	Output is correct
16	Correct	0 ms	612 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Incorrect	2 ms	720 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	129 ms	9532 KB	Output is correct
12	Correct	122 ms	9752 KB	Output is correct
13	Correct	74 ms	8020 KB	Output is correct
14	Incorrect	87 ms	8016 KB	Output isn't correct
15	Halted	0 ms	0 KB	-