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 pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
ll m;
vl a, b;
bool check(ll atleast){
ll use = 0;
vl cur(n);
for(int i = 0; i < n; i++){
cur[i] = atleast;
if(a[i] <= b[i]){
use += m;
continue;
}
ll here = min(m, (atleast-1) / a[i] + 1);
use += m - here;
cur[i] = max(0LL, atleast - here * a[i]);
}
for(int i = 0; i < n; i++){
if(cur[i] == 0) continue;
ll here = (cur[i]-1)/b[i] + 1;
use -= here;
if(use < 0) return false;
}
return use>=0;
}
int main(){
cin>>n>>m;
a.resize(n);
b.resize(n);
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, ans;
while(l <= r){
ll mid = l + (r - l) / 2;
bool can = check(mid);
if(can){
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout<<ans<<endl;
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... |