printРабочее место участника

printЗадачи

2246. Робот

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Компания "Филипп индастриз" отправила на Марс новый робот-марсоход. Целью робота является исследование поверхности Марса.
Для исследования Марса робот будет перемещаться по поверхности планеты на север и на юг вдоль прямой. Программа робота состоит из `n` команд, каждая из которых описывается целым числом `a_i`. Каждое число `a_i` задаёт количество шагов, которое необходимо сделать роботу. Если `a_i\ >\ 0`, то робот совершает `|a_i|` шагов на север, если `a_i\ <\ 0`, то `|a_i|` шагов на юг. Робот исполняет команды последовательно, начиная с первой.
Однако по пути на Марс робот подвергся космическому излучению и его программа могла повредиться. Запустив процедуру тестирования памяти, ученые выяснили, что в программу было внесено от 0 до `k` ошибок следующего вида: число `a_i` оказалось заменено на `-a_i`. Тем не менее, приземлившись на Марс, робот выполнил свою, возможно поврежденную, программу.
Теперь для организации спасения робота ученые хотят выяснить, насколько далеко от точки, в которой он начал выполнение программы, робот мог оказаться в результате. Помогите им это выяснить.
В первой строке входного файла находятся два числа `n`, `k` (`1\ ≤\ k\ ≤\ n\ ≤\ 10^5`) – количество чисел в программе робота и максимальное количество ошибок.
Во второй строке входного файла находятся `n` чисел `a_i` (`-10^4\ ≤\ a_i\ ≤\ 10^4`, `a_i\ ≠\ 0`) – программа робота.
В единственной строке выходного файла выведите максимальное расстояние в шагах, на которое мог удалиться робот, выполнив все команды и совершив не более `k` ошибок.

Пример ввода 1

4 1
1 2 -1 -3

Пример вывода 1

5

Пример ввода 2

7 2
5 -3 7 9 -2 -8 -1

Пример вывода 2

29
В первом примере робот мог, например, выполнить программу `1,\ 2,\ -1,\ 3` и в результате удалиться на 5 шагов на север.

Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015
loading