Максимальная сумма осадков
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин в течение $T$ мин. Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин, а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Даны два входных файла — файл А и файл B. Каждый файл в первой строке содержит натуральное число $K$ — количество минут, которое должно пройти между двумя передачами показаний, а во второй строке — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В каждой из следующих $N$ строк находится одно целое неотрицательное число, не превышающее $100\,000, обозначающее количество осадков за соответствующую минуту.
Для каждого файла найдите максимальную сумму двух элементов последовательности, номера которых отличаются не менее чем на $K$. Запишите сначала значение для файла А, затем значение для файла B.
Типовой пример: при $K=3$ и последовательности $15, 10, 200, 0, 30$ максимальная сумма равна $45$ — это сумма значений на первой и пятой минутах.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных пар.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждого текущего элемента нужно знать максимальный элемент, который находится не ближе чем на $K$ позиций раньше.
2Наводящая — какие числа считатьуровень 2 из 3
Поддерживайте максимум среди элементов с индексами от $0$ до $i-K$ и обновляйте его при переходе к следующему элементу.
3Прямая — фактически решениеуровень 3 из 3
Для каждого $i \geq K$ вычисляйте сумму $a_i + \max(a_0, a_1, \ldots, a_{i-K})$. Максимум всех таких сумм и есть ответ.