In this problem, you're given $n$ machines and asked the minimum time these machines need to work to create $t$ products such that the $i$-th machine creates a product in $k_i$ time.

Binary Search

Observe that the time needed to create at least $x$ products is monotonic. In other words, if the given machines can create $x$ products in $y_1$ time, then the same machines can create at least $x$ products in $y_2 > y_1$ time. Using this property, we can binary search over the answer. Read this module for more information.

For some value we binary search for, $ans$, we are left with the task of checking whether we can create $t$ products in $ans$ time. To do this, observe that it's optimal for every machine to work simultaneously. Then, in $ans$ time, machine $i$ can create $\lfloor \frac{ans}{k_i} \rfloor$ products.

Overall, the $n$ machines can create ‎‎$\sum_{i=1}^{n} \lfloor \frac{ans}{k_i} \rfloor$ products. If this sum $\geq t$, then $ans$ is valid.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first