Editorial

Навчимось перевіряти, чи можна вибрати набір пісень, що в нього відношення суми рейтингу до суми тривалості більше або дорівнює $x$ .

\frac{\sum _{i \in X} r _{i}}{\sum _{i \in X} t _{i}} \geq x

i \in X \sum r_{i} \geq x \cdot i \in X \sum t_{i}

i \in X \sum (r_{i} - t_{i} \cdot x) \geq 0

Таким чином, завжди оптимально брати $k$ пісень, які мають найбільше значення різниці $r_{i} - t_{i} \cdot x$ .

Зробимо бінарний пошук по відповіді, будемо проходитись по масиву, сортувати й шукати суму перших $k$ . Якщо сума більше ніж $0$ , то можна отримати відповідь рівну $x$ , інакше ні.

Загальна асимптотика — $O (N lo g A lo g N)$ .