Здравствуйте! Пытаюсь сдать задачу "882. Губернатор" с сайта acmp.ru. Недавно я создавал аналогичный пост для другой задачи, под которым подсказали, что в задачах такого рода должен работать жадный алгоритм и нужно лишь определить предикат для сортировки.

В этой же задаче я понял, что ответ не зависит от K и необходимо минимизировать сумму:

Здесь индексами обозначена последовательность взятия.

Я генерировал маленькие случайные тесты, для которых можно перебрать все n! перестановок и пробовал подобрать предикат, но все безрезультатно. Максимально близко к случайным тестам размера 10 подошел предикат , где — произведение всех a_i. На этом идеи кончились и нужна помощь. Может из-за маленького n решение предполагает динамику за O(n²) времени с памятью O(n), но с ней тоже не вяжется.