Задача №115417. Перекошенное разбиение
Дан массив \([a_1, a_2, \ldots, a_n]\), состоящий из неотрицательных целых чисел.
Рассмотрим разбиение массива на \(k\) непустых отрезков подряд идущих элементов. Назовем перекосом разбиения разность между максимальной и минимальной суммой чисел в отрезках разбиения. Требуется найти максимальный перекос разбиения данного массива на \(k\) подотрезков.
Например, если массив равен \([2, 1, 3, 4]\), то у разбиения \([2, 1, 3][4]\) перекос равен \(6-4=2\), у разбиения \([2, 1] [3, 4]\) перекос равен \(7-3=4\), а у разбиения \([2] [1, 3, 4]\) перекос равен \(8-2=6\). Последний вариант является оптимальным среди всех разбиений массива на два непустых отрезка.
Первая строка содержит два целых числа \(n\) и \(k\) (\(2 \le k \le n \le 300\,000\)) — длину массива и количество подотрезков, соответственно.
Вторая строка содержит \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — элементы массива.
Выведите одно число — максимальный перекос разбиения данного массива на \(k\) отрезков.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 11 | \(n \le 15\) | первая ошибка | |
| 2 | 11 | \(k = 2\) | первая ошибка | |
| 3 | 21 | \(k = 3\) | первая ошибка | |
| 4 | 15 | \(n \le 300\) | 1 | первая ошибка |
| 5 | 21 | \(n \le 3\,000\) | 1, 4 | первая ошибка |
| 6 | 21 | — | 1–5 | первая ошибка |
Первый пример разобран в условии задачи.
Во втором примере оптимальным разбиением является \([2][1][3, 4][1]\). Максимальная сумма на подотрезках в данном разбиении равна \(3 + 4 = 7\), минимальная сумма равна \(1\), таким образом, перекос равен \(6\).
4 2 2 1 3 4
6
5 4 2 1 3 4 1
6