Розбір
Навчимось перевіряти, чи можна вибрати набір пісень, що в нього відношення суми рейтингу до суми тривалості більше або дорівнює .
Таким чином, завжди оптимально брати пісень, які мають найбільше значення різниці .
Зробимо бінарний пошук по відповіді, будемо проходитись по масиву, сортувати й шукати суму перших . Якщо сума більше ніж , то можна отримати відповідь рівну , інакше ні.
Загальна асимптотика — .