Максимальная сумма подпоследовательности
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, сумма элементов каждой из которых кратна $k=71$. Найдите среди них подпоследовательность с максимальной суммой и определите её длину. Если таких подпоследовательностей найдено несколько, укажите количество элементов самой короткой из них.
Даны два входных файла — файл А и файл B. Каждый файл содержит в первой строке количество чисел $N$ ($1 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно натуральное число, не превышающее $10\,000$.
Для обработки файла B не следует использовать переборный алгоритм для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Как выразить сумму непрерывной подпоследовательности через префиксные суммы?
2Наводящая — какие числа считатьуровень 2 из 3
Две префиксные суммы дают сумму, кратную $71$, если имеют одинаковые остатки при делении на $71$.
3Прямая — фактически решениеуровень 3 из 3
Для каждого остатка храните первую позицию и минимальную префиксную сумму, а также последнюю позицию и максимальную префиксную сумму. При обработке очередной префиксной суммы проверяйте подпоследовательность с каждым ранее встреченным таким же остатком.