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 int __int128
#define ll long long
// O(N log(MAXN)) = O(60N)
const int N = 3e5 + 10;
ll a[N],b[N];
ll n,m;
bool check(int mid,bool debug){
int c = 0;
for(int i = 0;i<n;i++){
// We have to reach a minimum of mid
if(a[i] > b[i]){
int mx = (mid + a[i] - 1)/a[i];
mx = min(mx,(int)m);
if(mid < mx*a[i]){
c += mx;
continue;
}
int temp = mid - mx*a[i];
int temp123 = max((temp + b[i] - 1)/b[i],(int)0);
c += mx + temp123;
}
else{
int mx = (mid + b[i] - 1)/b[i];
c += mx;
}
}
if(c <= n*m)
return true;
else
return false;
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
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 = 2e18;
while(l < r){
int mid = (l + r + 1)/2;
if(check(mid,false))
l = mid;
else
r = mid - 1;
}
// check(r,true);
assert(check(r,false));
while(check(r + 1,false))
r++;
cout << r << "\n";
}
# | 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... |