Розклад#43

Розклад (Editorial)

Спершу зауважимо, що при фіксованому значенні M = \max(e) решта задачі розпадається на незалежні доданки.

Справді, кожне e_i має лежати в , а доданок |r_i - e_i| \cdot c_i мінімізується вибором найближчого до r_i допустимого значення:

  • якщо r_i \le M, беремо e_i = r_i і платимо ;

  • якщо r_i > M, беремо e_i = M і платимо (r_i - M) \cdot c_i.

Отже, загальна вартість при заданому дорівнює

F(M) = \sum_{i:\; r_i > M} (r_i - M)\, c_i \;+\; M \cdot k.

(Формально може виявитись меншим за , але це лише зменшує вартість, і такий випадок усе одно врахується іншим кандидатом.)

Тепер помітимо, що — кусково-лінійна функція від , злами якої розташовані рівно в точках r_i. Тому мінімум досягається в одній із точок множини \{0\} \cup \{r_1, \ldots, r_n\}, і достатньо перебрати ці n+1 кандидатів.

Щоб кожен кандидат обчислювався за , відсортуємо задачі за і побудуємо суфіксні суми двох величин: \sum c_i та \sum r_i c_i. Тоді для M = r_{i-1} (тобто коли «зрізаються» задачі з індексами )

F(M) = \Bigl(\sum_{j \ge i} r_j c_j\Bigr) - M \cdot \Bigl(\sum_{j \ge i} c_j\Bigr) + M \cdot k.

Відповідь — мінімум по всіх кандидатах.

Складність — \mathcal{O}(n \log n) через сортування. Стежте за типами: n \le 10^6, а добутки r_i c_i великі, тому суми накопичуйте у 64-бітному типі й ініціалізуйте відповідь достатньо великою «нескінченністю».