Перекошенное разбиение
(Время: 1 сек. Память: 32 Мб Сложность: 39%)
Дан массив [a1, a2, ... , an], состоящий из неотрицательных целых чисел.
Рассмотрим разбиение массива на 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. Последний вариант является оптимальным среди всех разбиений массива на два непустых отрезка.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и k (2 ≤ k ≤ n ≤ 300 000) – длину массива и количество подотрезков, соответственно.
Вторая строка содержит n целых чисел ai (0 ≤ ai ≤ 109) – элементы массива.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – максимальный перекос разбиения данного массива на k отрезков.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4 2 2 1 3 4 | 6 |
2 | 5 4 2 1 3 4 1 | 6 |
Пояснение к примерам
Первый пример разобран в условии задачи.
Во втором примере оптимальным разбиением является [2][1][3, 4][1]. Максимальная сумма на подотрезках в данном разбиении равна 3 + 4 = 7, минимальная сумма равна 1, таким образом, перекос равен 6.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|