Question

Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги, для каждой из *N* её метровых отметок. Нумерация отметок начинается с единицы.Проектировщикам необходимо выбрать участок дороги длиной не менее *К* метров, на котором значение суммы всех высот, выраженное в миллиметрах, максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка дороги с меньшим номером.Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее *К* метров, а оценка соответствующего участка дороги — максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки, выраженное в миллиметрах.**Входные данные.**Файл АФайл В

Даны два входных файла (файл *А* и файл *В*), каждый из которых в первой строке входных данных задаётся протяженность дороги *N* (1 ≤ *N* ≤ 10 000), а во второй — натуральное число *К* — минимально допустимое расстояние (в метрах) между двумя отметками дороги (*N* > *К*).В каждой из следующих *N* строк находится одно целое число, не превышающее по модулю 10 000 000: высота относительно уровня начального участка дороги (в миллиметрах) на соответствующей метровой отметке дороги.В ответе укажите два числа: сначала значение искомой величины для файла *А*, затем — для файла *В*.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги для каждой из N её метровых отметок. Нумерация отметок начинается с единицы.

Проектировщикам необходимо выбрать участок дороги длиной не менее K метров, на котором значение суммы всех высот (в миллиметрах) максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка с меньшим номером.

Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее K метров, а оценка соответствующего участка — максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки (в миллиметрах).

**Входные данные.**

Даны два входных файла (файл А и файл В). В первой строке каждого файла задаётся протяженность дороги N (1 ≤ N ≤ 10 000), а во второй — натуральное число K — минимально допустимое расстояние (в метрах) между двумя отметками дороги (N > K).

В каждой из следующих N строк находится одно целое число, не превышающее по модулю 10 000 000: высота относительно уровня начального участка дороги (в миллиметрах) на соответствующей метровой отметке.

**Выходные данные.**

В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла В.

### РЕШЕНИЕ

Идея решения: использовать префиксные суммы и скользящее окно для отслеживания минимальной суммы на префиксе, что позволяет за один проход найти максимальную сумму на участке длины не менее K.

Обозначим через $s[i]$ сумму высот с первой по i-ю отметку (префиксная сумма). Сумма высот на участке от отметки $i$ до отметки $j$ (включительно) равна $s[j] - s[i-1]$.

Нам нужно найти максимум выражения $s[j] - s[i-1]$, где $j - i \geq K - 1$ (то есть расстояние между отметками не менее K метров). Это эквивалентно минимизации $s[i-1]$ для каждого фиксированного $j$.

Алгоритм:
1. Вычислить массив префиксных сумм.
2. Для каждой позиции $j$ от K до N, отслеживать минимальное значение префиксной суммы среди всех допустимых начальных позиций (не ближе чем на K-1 позиций назад).
3. Вычислить оценку участка как разность текущей префиксной суммы и найденного минимума.
4. Вернуть максимальную оценку.

```python
f = open('27.txt')
N = int(f.readline())
K = int(f.readline())
d = [int(x) for x in f]

maxi = -10**10
ras = 10**10
s = [0] * N

for i in range(N):
    s[i] = s[i - 1] + d[i]

for j in range(K, N):
    ras = min(ras, s[j - K])
    maxi = max(maxi, s[j] - ras)

print(maxi)
```

Сложность: $O(n)$ — один проход для вычисления префиксных сумм и один проход для поиска максимума.

### ОТВЕТ

Задание №27ПрограммированиеЕГЭ по информатике