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