Submission #527313

#	Time	Username	Problem	Language	Result	Execution time	Memory
527313		ac2hu	Self Study (JOI22_ho_t2)	C++14	100 / 100	393 ms	9672 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long 
// O(N log(MAXN)) = O(60N)
const int N = 3e5 + 10;
int a[N],b[N];
int n,m;
bool check(int mid,bool debug){
	if(debug)
		cout << mid << "---> \n";
	int c = 0;
	for(int i = 0;i<n;i++){
		// We have to reach a minimum of mid	
		if(a[i] > b[i]){
			int mx = (mid + a[i] - 1)/a[i];
			mx = min(mx,m);
			if(mid < mx*a[i]){
				c += mx;
				continue;
			}
			int temp = mid - mx*a[i];
			int temp123 = max((temp + b[i] - 1)/b[i],0ull);
			c += mx + temp123;
			if(debug)
				cout << mx << " " << temp123 << "\n";
		}
		else{
			int mx = (mid + b[i] - 1)/b[i];
			c += mx;
			if(debug)
				cout << mx << "\n";
		}
	}
	if(c <= n*m)
		return true;
	else
		return false;
}
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n >> m;
	for(int i =0;i<n;i++)cin >> a[i];
	for(int i = 0;i<n;i++)cin >> b[i];
	int l = 0,r = 2e18;
	while(l < r){
		int mid = (l + r + 1)/2;
		if(check(mid,false))
			l = mid;
		else 
			r = mid - 1;
	}
	// check(r,true);
	assert(check(r,false));
	while(check(r + 1,false))
		r++;
	cout << r << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9