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