Кризис на планете Шелезяка

Для каждого момента получения смазки посчитаем урон. Сначала посчитаем урон, который получит робот, если получит порцию смазки до перетаскивания $$$1$$$-го ящика. Урон равен $$$d = \sum \limits_{i=1}^n a_i \cdot (n + 1 - i)$$$ (формула в 1-индексации). Теперь посмотрим на то, как поменяется урон, если мы получим порцию смазки после $$$1$$$-го ящика. Все ящики кроме $$$1$$$-го повредят робота на 1 день больше, а $$$1$$$-й вместо $$$n$$$ раз повредит робота лишь $$$1$$$ раз. То есть урон $$$d'$$$ можно посчитать из $$$d$$$ таким образом: $$$d' = d + (sum - a_1) - a_1 \cdot (n - 1) = d + sum - a_1 \cdot n$$$, где $$$sum$$$ — сумма чисел в массиве $$$a$$$.

Таким образом можно посчитать урон для всех возможных моментов получения смазки. Пусть $$$d_i$$$ — урон, который получит робот, если он получает порцию смазки перед перетаскиванием ящика $$$i$$$. Тогда $$$d_{i+1} = d_i + sum - a_i \cdot n$$$, то есть мы можем быстро насчитать урон для всех моментов получения смазки. Ответом на задачу будет минимум в этом массиве. Время работы этого решения составит $$$O(n)$$$.