Задача 6796. Источник: Поляков. Задание КИМ 27
(ЕГЭ-2023) По каналу связи передаётся последовательность целых чисел - показания прибора. В течение N минут (N – натуральное число) прибор ежеминутно регистрирует значение силы тока (в условных единицах) в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее К минут, а сумма этих чисел была максимально возможной. Запишите в ответе найденную сумму.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество переданных показаний, и натуральное число К (K < N) – минимальное количество минут, которое должно пройти между моментами передачами любых двух из трёх показаний. В каждой из следующих N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение силы тока в соответствующую минуту.
Пример входного файла:
6 2
15
14
20
23
21
10
При таких исходных искомая величина равна 56 – это сумма значений, зафиксированных на первой, третьей и пятой минутах измерений. Ответ: 56.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Начнем перебор с минимального индекса третьего элемента. На каждом шаге найдем максимальный элемент на дистанции 2 * k от третьего, максимальную сумму пары на дистанции k и максимальную сумму тройки.
Python
f = open("27-166b.txt")
n, k = map(int, f.readline().split())
a = [int(x) for x in f]
one = 0
two = 0
three = 0
for i in range(2 * k, n):
one = max(one, a[i - 2 * k])
two = max(two, one + a[i - k])
three = max(three, two + a[i])
print(three)
PascalABC
var
n, k, one, two, three, i: Integer;
a: array [1..170656] of Integer;
f: TEXT;
begin
Assign(f, '27-166b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i]);
one := 0;
two := 0;
three := 0;
for i := 2 * k + 1 to n do
begin
if a[i - 2 * k] > one then
one := a[i - 2 *k];
if one + a[i - k] > two then
two := one + a[i - k];
if two + a[i] > three then
three := two + a[i];
end;
Writeln(three);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-166b.txt");
int n, k;
f >> n >> k;
int* a = new int[n];
for (int i = 0; i < n; i++)
f >> a[i];
int one = 0, two = 0, three = 0;
for (int i = 2 * k; i < n; i++)
{
if (a[i - 2 * k] > one)
one = a[i - 2 * k];
if (one + a[i - k] > two)
two = one + a[i - k];
if (two + a[i] > three)
three = two + a[i];
}
cout << three << endl;
delete[] a;
}
Ответ
280212 26997