ЗАДАЧА E
Заготовка сена
| Имя входного файла: | hay.in |
| Имя выходного файла: | hay.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
А Матроскин Гаврюшу обучал. Учил его всему. Палку в воду бросит, а теленок принесет. Скажет ему: «Лежать!» - и Гаврюша лежит. Прикажет ему Матроскин: «Взять! Куси!» – тот сразу бежит и бодаться начинает. Прекрасный сторожевой бык из него получался.
Э.Успенский «Дядя Федор, пес и кот», глава 19
Вместе с тем Гаврюша очень быстро растет, и аппетит у него – будь здоров. Так что кот Матроскин кроме тренировки Гаврюши занимается заготовкой сена для него, ну а теленок Гаврюша это сено ест. Матроскин каждый день записывает сумму прихода и расхода сена. Матроскин хочет иметь возможность быстро находить по своим записям период, за который запасы сена увеличились больше всего. Помогите ему в этом.
У Матроскина есть массив целых чисел, в котором индексом элемента массива является номер дня от начала записей (первый день имеет индекс 0), а значениями элементов – разность между приходом и расходом сена в соответствующий день. Матроскин хочет найти в своих записях такой период из нескольких дней подряд, за который запасы сена увеличились больше всего.
Входные данные
Первая строка входного файла содержит единственное натуральное число N (1 <= N <= 5000) – количество дней в записях Матроскина. Вторая строка содержит N целых чисел, по модулю не превосходящих 106 – значения «приход–расход» в каждый из дней. Числа разделяются пробелами. Хотя бы одно из данных N чисел неотрицательно.
Выходные данные
В первую строку выходного файла выведите три целых числа – максимальную сумму за некоторый период времени, индекс начала периода времени и индекс конца периода. Индексы нумеруются с нуля. Во вторую строку выходного файла через пробел выведите значения «приход-расход» за этот период времени. Если существует несколько периодов времени, за которые запасы сена увеличились больше всего, то выведите более длинный из них. Если и таких периодов несколько, то выведите период с меньшим индексом начала.
Пример
| hay.in | hay.out |
|---|---|
|
|
|
|
Данная задача была любезно предоставлена компанией NIX Solutions (http://www.nixsolutions.com/)