#include <bits/stdc++.h>
using namespace std;
#define int long long
bool is_possible(int x, const vector<int>& a, const vector<int>& b, const vector<int>& enum_order, int m) {
int extra = 0;
int n = a.size();
for (int i : enum_order) {
int p = max(a[i], b[i]);
if (b[i] >= a[i]) p = b[i];
else p = a[i];
int op = (x + p - 1) / p; // ceil(x / p)
if (op <= m) {
extra += (m - op);
continue;
}
int needed = min(x - m * p, extra * (int)b[i]);
op = (x - needed + p - 1) / p;
if (op > m) return false;
extra -= (needed + b[i] - 1) / b[i];
}
return true;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int& ai : a) cin >> ai;
for (int& bi : b) cin >> bi;
vector<int> enum_order(n);
for (int i = 0; i < n; ++i) enum_order[i] = i;
sort(enum_order.begin(), enum_order.end(), [&](int i, int j) {
return max(a[i], b[i]) > max(a[j], b[j]);
});
int l = 0, r = numeric_limits<int>::max();
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (is_possible(mid, a, b, enum_order, m))
l = mid;
else
r = mid;
}
cout << l << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |