Submission #1263779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263779		goulthen	Self Study (JOI22_ho_t2)	C++20	100 / 100	206 ms	7484 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; ++i)

const int MAXN = 3e5+10;
int a[MAXN],b[MAXN];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);

	int n,m;cin >> n >> m;
	rep(i,1,n) cin >> a[i];
	rep(i,1,n) cin >> b[i];

	int lo = 1, hi = 1e18, ans;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;

		int cnt = n*m;
		vector<int> lvl(n+1,0);
		rep(i,1,n) {
			if (a[i] <= b[i]) continue;

			int k = min(m,(mid+a[i]-1)/a[i]);
			cnt -= k;
			lvl[i] += k*a[i];
		}
		bool ok = 1;
		rep(i,1,n) {
			if (lvl[i] >= mid) continue;
			int k = (mid-lvl[i]+b[i]-1)/b[i];
			if (cnt < k) {
				ok = 0;
				break;
			}
			cnt -= k;
		}

		if (ok) {
			ans = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}

	cout << ans << '\n';
}

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