Дана последовательность из
N
чисел. Известно, что сумма всех чисел последовательности не превышает 10
9. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратно
K = 11
. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Даны два входных файла (
файл A и
файл B), каждый из которых содержит в первой строке количество чисел
N
(1 <= N <= 1 000 000). Каждая из следующих
N
строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для
К=3
):
6
-1
2
3
-5
18
12
В этом наборе можно выбрать следующие подпоследовательности, с количеством положительных элементов кратных
K=3
:
-1 + 2 + 3 + (-5) + 18 = 17;
2 + 3 + (-5) + 18 = 18;
3 + (-5) + 18 + 12 = 28
.
Ответ (для
K = 3
):
28
.
Предупреждение: для обработки файла
B
не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.