# VACCNE - Editorial

Contest
Author: Tejus Kaw
Tester: Rahul Sharma
Editorialist: Tejus Kaw

Easy

# PREREQUISITES:

Binary Search

#### QUICK EXPLANATION :

HERE BASICALLY WHAT WE ARE DOING IS THAT WE ARE FIXING THE MAXIMUM AMOUNT OF FINE IN N DAYS AND AFTER GIVING THE FINE WE HAVE TO CHECK WHETHER THE REQUIRED VACCINES IN TOTAL IS LESS THAN M OR NOT . FOR FINDING k(maximum fine in n days) we can simply use lower_bound of binary search.

# EXPLANATION :

In starting the approach will be of using a heap and in each iteration , the one with maximum total_fine , we will give a vaccine.But on seeing the Constraints it will lead to TLE.

If on the i^{th} day, the city is given x_i vaccines, then city is given a minimum of c_i = max(0,( A[i]-x_i) \cdot B[i]) fine too. Let’s invert this, if the city is given c_i fine on the i^{th} day, then we need to give city at least max(0,A[i]-floor(c_i/B[i])) more vaccines too.

Now, let’s fix a particular value of the maximum fine I’m going give over all days. Let this value be k, i.e assume max( c_1,c_2...c_n ) = k. So, we just assume now, that we give k amount of fine each day, i.e c_i=k for all i, since giving more fine is always going to help us use lesser vaccine , and the maxima over the N days is still k.

Then, on day i, the city requires at least max(0,A[i]-(k/B[i])) more vaccines , But remember, we cannot have extra vaccines . So, we need sum of the max(0,A[i]-(k/B[i])) to be \le M . So, we need to find the minimum value of k, such that considering it we give city minimum number of vaccines required each day after giving k amount of fine, then that sums to a number \le M .

while(low < high)
{
int mid=(low+high)/2;

long long now=0;

for(int i=0;i < n;i++)
{
long long curr=max(0,A[i]-(mid/B[i])));

now+=curr;
}

if(now<=m)
{
high=mid;
}

else
{
low=mid+1;
}
}


### TIME COMPLEXITY :

O(N \cdot log (10^{18})). Why setting high=10^{18} works : Consider the worst case, N=10^5, M=0, A[i]=10^9 , B[i]=10^9, 1 \le i \le N. REMEMBER A[i]⋅B[i] can be 10^{18}.

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(1e5+5);
const ll mod=(ll)(1e9+7);
ll a[maxn],b[maxn];
int n;ll m;
bool check(ll mid)
{

for(int i=0;i<n;i++)
{
ll now=a[i]-(mid/b[i]);

{
return false;
}
}

return true;
}

int main()
{
ios_base::sync_with_stdio(0);cin.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 low=0,high=(ll)(1e18);

while(low<high)
{
ll mid=(low+high)>>1;

if(check(mid))
{
high=mid;
}
else
{
low=mid+1;
}
}

cout<<low<<endl;

return 0;
}