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