Максимальная сумма без делимости
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек $N$ ($1 \leq N \leq 1\,000\,000$). Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $12\,000$.
Для приведённого в условии примера, если $k = 5$, искомая сумма равна 44. В ответе укажите значение искомой суммы для файла A, затем для файла B. Для обработки файла B нельзя использовать перебор всех возможных вариантов.
Вложенные файлы с исходными данными в предоставленном наборе отсутствуют, поэтому числовые значения ответов для файлов A и B определить невозможно.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Как хранить максимальную сумму для каждого возможного остатка по модулю $109$ после обработки очередного числа троек?
2Наводящая — какие числа считатьуровень 2 из 3
Используйте динамическое программирование: для каждого остатка храните максимальную достижимую сумму. При добавлении числа $x$ новый остаток равен $(r+x) \bmod 109$.
3Прямая — фактически решениеуровень 3 из 3
Инициализируйте $dp[0] = 0$, остальные значения — минус бесконечностью. Для каждой тройки постройте новый массив: $new[(r+x) \bmod 109] = \max(new[(r+x) \bmod 109], dp[r]+x)$. После обработки всех троек найдите максимум среди $dp[r]$ при $r \ne 0$.