Submission #706522

#	Time	Username	Problem	Language	Result	Execution time	Memory
706522		xuliu	Self Study (JOI22_ho_t2)	C++17	100 / 100	299 ms	10888 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define debug if(0)

const ll inf = 1e18+4;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n, m; cin>>n>>m;
	vector<ll> 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 x) {
		// if can be done with minimum >= x
		__int128 res = 0;
		for(int i=0; i<n; i++) {
			ll y = 0;
			if(b[i] >= a[i]) y += (x+(b[i]-1))/b[i];
			else {
				ll t = (x+(a[i]-1))/a[i];
				if(t > m) {
					y += m;
					ll t2 = ((x-m*a[i])+(b[i]-1))/b[i];
					y += t2;
				} else y += t;
			}
			res += y;
		}
		//debug cerr<<"x: "<<x<<", res = "<<res<<" ; n*m = "<<n*m<<"\n";
		return res <= (n*m);
	};
	ll lo = 0, hi = inf;
	while(lo < hi) {
		ll m = (lo+hi+1)/2LL;
		if(check(m)) lo = m;
		else hi = m-1;
	}
	cout<<lo<<"\n";
}

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