Розкол платить L \times R — це рівно кількість пар шматочків, які він уперше розділив, зважена їхніми м'ясистостями. Кожна пара розділяється рівно один раз — у той момент, коли розколюється фрагмент, що їх обох містить. Тому порядок розколів не має значення, а сумарне задоволення дорівнює сумі a_i a_j по всіх парах, що опинилися в різних кінцевих фрагментах:
де — сума всього масиву, а S_p — суми фрагментів. Рівно розколів дають рівно k + 1 фрагментів, тож задача звелася до мінімізації суми квадратів сум k+1 послідовних фрагментів.
Цей мінімум опуклий за кількістю фрагментів, тому працює «трюк з митом»: додамо штраф за кожен фрагмент і двійковим пошуком знайдемо , за якого оптимальною стає саме k+1 фрагментів. За фіксованого маємо
де — префіксні суми. Це мінімум по прямих y = -2P_i x + (f[i] + P_i^2) у точці x = P_j; оскільки a_i \ge 0, масив не спадає, тож і нахили спадають, і запити зростають — досить опуклої оболонки з двома вказівниками. Відповідь — f[n] - \lambda(k+1).
Зверніть увагу на переповнення: S^2 сягає 10^{18}, тож порівняння всередині оболонки варто робити в 128-бітних цілих.
Складність: O(n \log S^2).
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.