This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MN = 300001;
const ll INF = 1e18 + 71;
ll n, m, A[MN], B[MN];
ll mini = INF;
bool ok(ll val, int dbg) {
if(!val) return 1;
ll nr_sar = 0;
for(int i = 1; i <= n; ++i) {
if((val - 1) / A[i] + 1 <= m) {
nr_sar += m - ((val - 1) / A[i] + 1);
if(dbg) {
assert((m - ((val - 1) / A[i] + 1) == 0));
}
assert((m - ((val - 1) / A[i] + 1)) >= 0);
} else {
nr_sar -= (val - m * A[i] - 1) / B[i] + 1;
assert(((val - m * A[i] - 1) / B[i] + 1) >= 0);
}
if(nr_sar < - n * m) return 0;
if(dbg) assert(!(nr_sar > 0));
}
return (nr_sar >= 0);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> A[i];
for(int i = 1; i <= n; ++i) {
cin >> B[i];
if(A[i] < B[i]) A[i] = B[i];
}
for(int i = 1; i <= n; ++i) mini = min(A[i], mini);
ll st = 0, dr = INF, mij;
while(st < dr) {
mij = st + (dr - st + 1) / 2;
if(ok(mij, 0)) {
st = mij;
} else dr = mij - 1;
}
if(m == 1) {
ok(st, 1);
assert(st == mini);
cout << st << "\n";
} else
cout << st << "\n";
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... |