Let ~F_i(x) = -L_ix^2 + S_ix - M_i~ be the flavor rating of the ~i^{th}~ recipe with ~x~ mL of water added, ~C_i(x) = x~ be the cost for the ~i^{th}~ recipe to add ~x~ mL of water, and ~T~ be the set of indices of the selected recipe.

Essentially, our objective is to find the maximum value of ~\frac{\sum_{i=1}^{K}F_{T_i}(x)}{\sum_{i=1}^{K}C_{T_i}(x)}~. We can solve this problem by binary search the answer ~mid~.

$$\displaystyle \frac{\sum_{i=1}^{K}F_{T_i}(x)}{\sum_{i=1}^{K}C_{T_i}(x)} \geq mid$$ $$\displaystyle \sum_{i=1}^{K}F_{T_i}(x) \geq mid \times \sum_{i=1}^{K}C_{T_i}(x)$$ $$\displaystyle \sum_{i=1}^{K}F_{T_i}(x) - mid \times \sum_{i=1}^{K}C_{T_i}(x) \geq 0$$ $$\displaystyle \sum_{i=1}^{K}F_{T_i}(x) - \sum_{i=1}^{K}(mid \times C_{T_i}(x)) \geq 0$$ $$\displaystyle \sum_{i=1}^{K}(F_{T_i}(x) - mid \times C_{T_i}(x)) \geq 0$$ $$\displaystyle \sum_{i=1}^{K}(-L_{T_i}x^2 + S_{T_i}x - M_{T_i} - mid \times x) \geq 0$$ $$\displaystyle \sum_{i=1}^{K}(-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}) \geq 0$$

Then we can find the maximum value of the expression on the left side of the inequality. If the maximum value is greater than or equal to ~0~, we can say that ~mid~ is possible. Our goal now turns to finding the maximum possible value ~mid~, which can be simply done with binary search.

Observing that to maximize the expression ~\sum_{i=1}^{K}(-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i})~, our strategy is to prioritize the first ~K~ recipes with higher values of ~-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}~. Additionally, notice that ~-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}~ is a quadratic function in terms of ~x~, we can find the maximum value of it by find the vertex. Be careful that we should take the ~y~-intercept instead of the vertex if the vertex have a negative ~x~ value.

Time Complexity: ~\mathcal{O}(N\log{N}\log{\frac{1}{\epsilon}})~