Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Перекошенное разбиение

(Время: 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.TXTOUTPUT.TXT
14 2
2 1 3 4
6
25 4
2 1 3 4 1
6

Пояснение к примерам

Первый пример разобран в условии задачи.

Во втором примере оптимальным разбиением является [2][1][3, 4][1]. Максимальная сумма на подотрезках в данном разбиении равна 3 + 4 = 7, минимальная сумма равна 1, таким образом, перекос равен 6.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Кузнечик 2D
 B. Простоватые числа
 C. Кислотные дожди
 D. Поиск сокровищ
 E. Разность квадратов
 F. Перекошенное разбиение
 G. Главное правило личных олимпиад
 H. Туристический маршрут

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru