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;
#define ll long long
#define ar array
const int mxN = 3e5+5, M = 1e9+7;
ll n, m, a[mxN], b[mxN];
bool f(ll val){
ll ret = 0;
for(int i = 0; i<n; ++i){
if(a[i] <= b[i]){
ret += (val+b[i]-1)/b[i];
}
else{
ll flag = (val+a[i]-1)/a[i];
ll upd = 1e18;
for(ll j = max(flag-2, 0ll); j<=flag; ++j){
ll rem = max(0ll, val - a[i]*j);
upd = min(upd, j + (rem+b[i]-1)/b[i]);
}
ret += upd;
}
if(ret > n*m) return 0;
}
return 1;
}
int main(){
#ifdef _DEBUG
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
cin >> n >> m;
for(int i = 0; i<n; ++i){
cin >> a[i];
}
for(int i = 0; i<n; ++i){
cin >> b[i];
}
ll l = 0, r = 1e18;
while(l != r){
ll m = (l+r+1)/2;
if(f(m)){
l = m;
}else{
r = m-1;
}
}
cout << l;
}
# | 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... |