Submission #1136746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136746		nuutsnoynton	Self Study (JOI22_ho_t2)	C++20	100 / 100	307 ms	7468 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = unsigned long long;
const ll N = 3e5 + 2;
ll a[N], b[N], val[N], n, m;

bool Solve(ll X) {
	ll i, s, r, left = n * m;
	for (i = 1; i <=n; i ++){
		val[i] = X;
		if ( a[i] >= b[i]) {
			s = a[i] * m; 
			if ( s < X) {
				val[i] = X - s;
				left -= m;
			}
			else {
				r = (X - 1)/a[i] + 1;
				r = min(r, m);
				s = r * a[i];
				val[i] = 0;
				left = left - r;
			}
		}
	}
	for (i = 1; i <=n; i ++) {
		if ( val[i] <= 0) continue;
		r = ((val[i]) - 1)/b[i] + 1;
		if ( left >= r) left -= r;
		else return false;
	}
	if ( left >= 0) return true;
	return false;
}

int main() {
	ll r, x, y, i, lo, hi, mid, j, ans, t;

	cin >> n >> m;
	
	
	for (i = 1; i <= n; i ++) cin >> a[i];
	for (i = 1; i <= n; i ++) cin >> b[i];
	lo = 0;
	hi = 2e18 + 1;
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if ( Solve(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo - 1 <<endl;
}

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