Question

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

Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее K мин., а их произведение было максимально возможным. В ответе запишите найденное произведение.

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

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

Accepted Answer

Answer

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

Алгоритм работает в один проход по массиву. На каждом шаге i мы:
1. Обновляем переменную m — максимум среди элементов с индексами от 0 до i − K включительно.
2. Вычисляем произведение текущего элемента a[i] на m и обновляем глобальный максимум.

Таким образом, гарантируется, что между двумя выбранными числами пройдёт ровно K или более минут.

```python
with open('27_A.txt') as f:
    K = int(f.readline())
    N = int(f.readline())
    a = [int(f.readline()) for _ in range(N)]

m = 0
maxi = 0
for i in range(K, N):
    m = max(m, a[i - K])
    maxi = max(maxi, a[i] * m)

print(maxi)
```

Для файла B аналогично:

```python
with open('27_B.txt') as f:
    K = int(f.readline())
    N = int(f.readline())
    a = [int(f.readline()) for _ in range(N)]

m = 0
maxi = 0
for i in range(K, N):
    m = max(m, a[i - K])
    maxi = max(maxi, a[i] * m)

print(maxi)
```

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

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