Ключевой момент:↵
↵
x — сколько раз мы убрали два самых маленьких элемента.↵
↵
Тогда k — x — сколько раз мы убрали один самый большой.↵
↵
После x операций удаления двух маленьких: убрано 2*x элементов слева → l = 2*x.↵
↵
После (k-x) операций удаления больших: убрано (k-x) элементов справа → правый индекс = n — (k-x).↵
↵
p[r] — сумма первых r элементов.↵
↵
p[l] — сумма первых l элементов.↵
↵
Разность = сумма элементов от индекса l до r-1 (это оставшиеся элементы).↵
↵
Ищем максимум по всем вариантам x.↵
↵
Как понять:↵
Отсортировать массив.↵
↵
Посчитать префиксные суммы.↵
↵
Перебрать все возможные способы распределить k операций между:↵
↵
удалением двух маленьких↵
↵
удалением одного большого↵
↵
Для каждого способа посчитать сумму оставшихся.↵
↵
Взять максимум.↵
↵
x — сколько раз мы убрали два самых маленьких элемента.↵
↵
Тогда k — x — сколько раз мы убрали один самый большой.↵
↵
После x операций удаления двух маленьких: убрано 2*x элементов слева → l = 2*x.↵
↵
После (k-x) операций удаления больших: убрано (k-x) элементов справа → правый индекс = n — (k-x).↵
↵
p[r] — сумма первых r элементов.↵
↵
p[l] — сумма первых l элементов.↵
↵
Разность = сумма элементов от индекса l до r-1 (это оставшиеся элементы).↵
↵
Ищем максимум по всем вариантам x.↵
↵
Как понять:↵
Отсортировать массив.↵
↵
Посчитать префиксные суммы.↵
↵
Перебрать все возможные способы распределить k операций между:↵
↵
удалением двух маленьких↵
↵
удалением одного большого↵
↵
Для каждого способа посчитать сумму оставшихся.↵
↵
Взять максимум.↵
