Dadas's Ramen Mukbang

For a fixed $K$, define

$$f(K)=\sum_{i=1}^N \min(A_i,K).$$

As $K$ increases, every term $\min(A_i,K)$ is nondecreasing, so $f(K)$ is also nondecreasing. Therefore, we can binary-search for the smallest $K$ such that $f(K)\ge L$.

It is enough to use $\max A_i$ as the right endpoint of the search interval. Since the existence of a valid answer is guaranteed, the first $K$ with $f(K)\ge L$ must satisfy $f(K)=L$.

For each candidate $K$, we can compute $f(K)$ in $O(N)$ by scanning the array once. Since $A_i\le10^{13}$, the binary search uses at most about $44$ iterations. The total time complexity over all test cases is

$$O\left(\left(\sum N\right)\log 10^{13}\right),$$

and the extra space complexity is $O(N)$ per test case.

Also, $\sum A_i\le 2\cdot10^{18}$, so $f(K)$ and every related sum fit in a signed 64-bit C++ long long.

Solution written by GPT5.6