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