Submission #1216312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216312		trimkus	Self Study (JOI22_ho_t2)	C++20	100 / 100	162 ms	6312 KiB

Main

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




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int 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];
	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		return max(a[x], b[x]) > max(a[y], b[y]);
	});
	auto check = [&](ll need) -> bool {
		ll free = 0;
		//~ cerr << need << ":\n";
		for (auto& i : ord) {
			ll now = max(a[i], b[i]);
			ll have = (need + now - 1) / now;
			//~ cerr << now << " " << have << " " << free << "\n";
			if (have <= m) {
				free += m - have;
			} else {
				ll now_need = need - 1LL * m * now;
				now = b[i];
				ll add = (now_need + now - 1) / now;
				if (add > free) return false;
				free -= add; 
			}
		}
		return true;
	};
	ll left = 0, right = 1e18;
	ll res = -1;
	while (left <= right) {
		ll m = (left + right) / 2;
		if (check(m)) {
			left = m + 1;
			res = m;
		} else {
			right = m - 1;
		}
	}
	cout << res << "\n";
}

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