Question

По каналу связи передаётся последовательность целых чисел — показания прибора. В течение *N* мин. (*N* — натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее *K* мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.**Входные данные.**Файл AФайл B

Дано два входных файла (файл *A* и файл *B*), каждый из которых в первой строке содержит число *K* — минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй — количество переданных показаний *N*. В каждой из следующих *N* строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.В ответе укажите два числа: сначала значение искомой величины для файла *А*, затем — для файла *B*. *Пример организации исходных данных во входном файле:*26150-15020-200-3000При таких исходных данных искомая величина равна 170 — это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

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

Ответ:

Accepted Answer

Answer

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

По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения (в условных единицах) и передаёт его на сервер. Требуется найти три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а сумма этих трёх чисел была максимально возможной.

**Входные данные.** Два входных файла (файл A и файл B). Каждый файл в первой строке содержит число $K$ — минимальное количество минут между моментами передачи показаний. Во второй строке — количество переданных показаний $N$. В каждой из следующих $N$ строк находится одно целое число, по модулю не превышающее $10\,000\,000$, обозначающее значение напряжения в соответствующую минуту.

**Пример входных данных:**
```
2
6
150
-150
20
-200
-300
```

При таких исходных данных искомая величина равна 170 — это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

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

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

### РЕШЕНИЕ

Идея решения: использовать динамическое программирование, где для каждой позиции $i$ вычисляется максимальная сумма трёх элементов, выбранных с соблюдением ограничения на расстояние между ними.

Обозначим через $	ext{st}$ максимальное значение среди элементов, находящихся на расстоянии не менее $2K$ позиций назад от текущей позиции. Через $	ext{fin}$ обозначим максимальную сумму первого и второго элементов, где второй находится на расстоянии не менее $K$ позиций от первого. Тогда для каждой позиции $i$ (начиная с позиции $2K$) мы можем вычислить максимальную сумму трёх элементов как $	ext{fin} + a[i]$.

Алгоритм:
1. Инициализируем переменные $	ext{st}$, $	ext{fin}$ и $	ext{summa}$ нулевыми значениями.
2. Для каждой позиции $i$ от $2K$ до $N-1$:
   - Обновляем $	ext{st}$ как максимум текущего значения $	ext{st}$ и элемента $a[i-2K]$ (максимум среди элементов, достаточно далеко позади).
   - Обновляем $	ext{fin}$ как максимум текущего значения $	ext{fin}$ и суммы $	ext{st} + a[i-K]$ (максимум суммы первого и второго элементов).
   - Обновляем $	ext{summa}$ как максимум текущего значения $	ext{summa}$ и суммы $	ext{fin} + a[i]$ (максимум суммы всех трёх элементов).
3. Выводим результат.

```python
f = open('27_B_2024.txt')
k = int(f.readline())
n = int(f.readline())
a = [int(x) for x in f]

st = 0
fin = 0
summa = 0

for i in range(2 * k, n):
    st = max(st, a[i - 2 * k])
    fin = max(fin, st + a[i - k])
    summa = max(summa, fin + a[i])

print(summa)
```

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

### ОТВЕТ

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