(ЕГЭ-2023) Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги, для каждой из N её метровых отметок. Нумерация отметок начинается с единицы.
Проектировщикам необходимо выбрать участок дороги длиной не менее К метров, на котором значение суммы всех высот, выраженное в миллиметрах, максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка дороги с меньшим номером.
Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее К метров, а оценка соответствующего участка дороги – максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки, выраженное в миллиметрах.
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество метровых отметок, и натуральное число К (1 <K<N) – минимально допустимое расстояние (в метрах) между двумя отметками дороги. В каждой из следующих N строк находится одно целое число, не превышающее по модулю 10 000 000: высота относительно уровня начального участка дороги (в миллиметрах) на соответствующей метровой отметке дороги.
Пример входного файла:
5 2
-200
-50
500
100
-100
При таких исходных данных искомая величина равна –50 + 500 + 100 = 550 для участка дороги длиной 2 от 2-й до 4-й отметки. Ответ: 550.
Файл