10/04/2025 23:19:50

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

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

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

В первом примере робот мог, например, выполнить программу

$1,\ 2,\ -1,\ 3$ и в результате удалиться на 5 шагов на север.

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

25/10/2015	Региональные отборочные командные соревнования для школьников (H)
30/06/2023	Лето 2023-3 простые (командное) (C)
28/06/2024	Лето 2024-3 простые (командное) (C)