P9181 [COCI 2022/2023 #5] Flags

There are $n$ right triangles. The $i$-th right triangle has hypotenuse length $r_i$. The sum of the heights of these right triangles does not exceed $S$. Find the maximum possible total area of these $n$ right triangles.

The first line contains two integers $n, S\ (1\le n\le 10^5,1\le S\le 10^{10})$, representing the number of triangles and the maximum allowed sum of their heights. The second line contains $n$ integers $r_i\ (1\le r_i\le 10^5)$.

Output the maximum possible total area of these $n$ right triangles (keep $10$ digits after the decimal point). Your output is considered correct if its absolute error or relative error is at most $10^{-6}$ compared to the answer.

Explanation for sample $2$: The maximum possible case is a triangle with side lengths $6, 8, 10$, with area $24$. |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$0$|Sample only|$0$| |$1$|$n\le 100$|$37$| |$2$|$n\le 1000$|$20$| |$3$|No additional constraints|$43$| Translated by ChatGPT 5