АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1790. Выгодный бизнес

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Предприниматель Сигизмунд хранит сведения о прибыли своей фирмы за каждый день её работы с момента основания. Однако, дела в его компании идут не слишком хорошо, поэтому в некоторые дни прибыль может оказаться отрицательной.

Для поднятия настроения Сигизмунд решил найти самый длинный интервал времени, в котором суммарная прибыль была положительна. Помогите ему это сделать.

Входные данные

В первой строке входных данных записано натуральное число N – количество дней (1 ≤ N 105).

В следующей строке записаны через пробел N целых чисел p1, p2, ..., pN – прибыль компании в день 1, 2, ..., N ( -106 pi 106).

Выходные данные

Выведите одно натуральное число – максимальную длину найденного интервала, на котором суммарная прибыль больше нуля.

Пример ввода

8

1 -5 -1 2 -3 2 3 -4

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

5

Примечание.  В примере из условия положительная прибыль получилась на интервале длиной 5 дней, начиная с третьего дня: (-1) + 2 + (-3) + 2 + 3 = 3.

Система оценивания.

Подзадача 1 (30 баллов):  N ≤ 100

Подзадача 2 (30 баллов):  N ≤ 1000

Подзадача 3 (40 баллов):  N ≤ 105

Во всех подзадачах баллы даются, только если все тесты этой подзадачи пройдены.


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Школьные олимпиады Вологодской области / II Областная олимпиада на приз губернатора 2017 / Заключительный этап, 9-10 класс /
1789. C - Ребус 1790. 1791. E - Лягушка на полигоне
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.