Submission #937868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937868	2024-03-04T15:48:45 Z	Litusiano	Self Study (JOI22_ho_t2)	C++17	0 / 100	436 ms	7468 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

vector<pair<int,int>> v;
int n,m;
bool check(int mid){
	vector<int> need(n);
	int left = 0;
	for(int i = 0; i<n; i++){
		int z = max(v[i].first, v[i].second);
		int k = (mid+z-1)/z;
		need[i] = max(0ll,mid-(m * z));
		left+=max(0ll,m-k);
	}
	for(int i = 0; i<n; i++){
		if(need[i] <= 0) continue;
		left -= (need[i] + v[i].second - 1)/v[i].second;	
	}
	return left>=0;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	v.resize(n);
	for(auto& x : v) cin>>x.first;
	for(auto& x : v) cin>>x.second;
	int ans = LLONG_MAX;
	for(auto i : v){
		ans = min(ans,max(i.first,i.second));
	}
	int l = 0; int r = 2e18;
	while(r > l+1){
		int mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	cout<<l<<endl;
}	

Subtask #1

0 / 10.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	344 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	4 ms	348 KB	Output is correct
11	Correct	221 ms	7464 KB	Output is correct
12	Correct	232 ms	7456 KB	Output is correct
13	Correct	224 ms	7468 KB	Output is correct
14	Incorrect	436 ms	7464 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	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 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	544 KB	Output is correct
9	Correct	112 ms	3944 KB	Output is correct
10	Correct	75 ms	2652 KB	Output is correct
11	Correct	55 ms	2136 KB	Output is correct
12	Correct	45 ms	1704 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Incorrect	9 ms	348 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	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	344 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	4 ms	348 KB	Output is correct
11	Correct	221 ms	7464 KB	Output is correct
12	Correct	232 ms	7456 KB	Output is correct
13	Correct	224 ms	7468 KB	Output is correct
14	Incorrect	436 ms	7464 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	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 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	544 KB	Output is correct
9	Correct	112 ms	3944 KB	Output is correct
10	Correct	75 ms	2652 KB	Output is correct
11	Correct	55 ms	2136 KB	Output is correct
12	Correct	45 ms	1704 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Incorrect	9 ms	348 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	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	344 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	4 ms	348 KB	Output is correct
11	Correct	221 ms	7464 KB	Output is correct
12	Correct	232 ms	7456 KB	Output is correct
13	Correct	224 ms	7468 KB	Output is correct
14	Incorrect	436 ms	7464 KB	Output isn't correct
15	Halted	0 ms	0 KB	-