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