Спершу зауважимо, що при фіксованому значенні 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.
Отже, загальна вартість при заданому дорівнює
(Формально може виявитись меншим за , але це лише зменшує вартість, і такий випадок усе одно врахується іншим кандидатом.)
Тепер помітимо, що — кусково-лінійна функція від , злами якої розташовані рівно в точках r_i. Тому мінімум досягається в одній із точок множини \{0\} \cup \{r_1, \ldots, r_n\}, і достатньо перебрати ці n+1 кандидатів.
Щоб кожен кандидат обчислювався за , відсортуємо задачі за і побудуємо суфіксні суми двох величин: \sum c_i та \sum r_i c_i. Тоді для M = r_{i-1} (тобто коли «зрізаються» задачі з індексами )
Відповідь — мінімум по всіх кандидатах.
Складність — \mathcal{O}(n \log n) через сортування. Стежте за типами: n \le 10^6, а добутки r_i c_i великі, тому суми накопичуйте у 64-бітному типі й ініціалізуйте відповідь достатньо великою «нескінченністю».