Books#214

Books (Editorial)

Введемо для кожної книжки величину c_i = b_i - a_i — саме стільки задоволення дає прочитана книжка і стільки ж віднімається, якщо книжку не прочитати.

Нехай — множина прочитаних книжок, |R| = k. Тоді загальне задоволення дорівнює

\sum_{i \in R} c_i - \sum_{i \notin R} c_i.

Позначимо C = \sum_{i=1}^{n} c_i — сума по всіх книжках. Тоді другий доданок дорівнює C - \sum_{i \in R} c_i, і вираз перетворюється на

2 \sum_{i \in R} c_i - C.

Величина фіксована, тому максимізувати треба лише \sum_{i \in R} c_i — суму c_i по рівно обраних книжках. Очевидно, для цього треба взяти найбільших значень c_i.

Отже, розв'язок: порахувати всі c_i, відсортувати їх за спаданням, узяти суму перших , і вивести подвоєну цю суму мінус .

Зверніть увагу, що серед c_i бувають від'ємні, але це нічого не змінює: умова вимагає прочитати рівно книжок, тому навіть якщо всі c_i від'ємні, ми беремо найбільших (найменших за модулем).

Складність — \mathcal{O}(n \log n). Значення сягають 2 \cdot 10^9 за модулем, а сума — порядку 10^{14}, тому обов'язково беріть 64-бітний тип.