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)}\ge mid}$$ $${\displaystyle \sum _{i=1}^K{F}_{T_i}(x)\ge 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)\ge 0}$$ $${\displaystyle \sum _{i=1}^K{F}_{T_i}(x)-\sum _{i=1}^K(mid\times C_{T_i}(x))\ge 0}$$ $${\displaystyle \sum _{i=1}^K(F_{T_i}(x)-mid\times C_{T_i}(x))\ge 0}$$ $${\displaystyle \sum _{i=1}^K(-L_{T_i}{x}^2+S_{T_i}x-M_{T_i}-mid\times x)\ge 0}$$ $${\displaystyle \sum _{i=1}^K(-L_{T_i}{x}^2+(S_{T_i}-mid)x-M_{T_i})\ge 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}})~