Задача 6800. Источник: Поляков. Задание КИМ 27
(ЕГЭ-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.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
В данной задаче следует учитывать, что у участка длиной k будет k + 1 отметок. Традиционно, для решения задачи с суммированием некоторого интервала значений используем префиксные суммы. Однако, полный перебор пар префиксных сумм для второго файла вполне приемлемо работает на компилируемых языках (на C++ ответ получается за 1-2 секунды, на PascalABC за 15-20 секунд), но на Python такое решение работает несколько десятков минут.
Python
f = open("27-170b.txt")
n, k = map(int, f.readline().split())
p = [0]
for i in f:
p.append(p[-1] + int(i))
mx = 0
for i in range(n - k):
for j in range(i + k + 1, n + 1):
if p[j] - p[i] > mx:
mx = p[j] - p[i]
print(mx)
PascalABC
var
n, k, max, x, i, j: Integer;
p: array [1..166780] of Integer;
f: TEXT;
begin
Assign(f, '27-170b.txt');
Reset(f);
Readln(f, n, k);
p[1] := 0;
for i := 2 to n + 1 do
begin
Readln(f, x);
p[i] := p[i - 1] + x;
end;
max := -1000000000;
for i := 1 to n - k do
for j := i + k + 1 to n + 1 do
if p[j] - p[i] > max then
max := p[j] - p[i];
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-170b.txt");
int n, k;
f >> n >> k;
int* p = new int[166780];
p[0] = 0;
for (int i = 1; i <= n + 1; i++)
{
int x;
f >> x;
p[i] = p[i - 1] + x;
}
int max = -1000000000;
for (int i = 0; i < n - k; i++)
for (int j = i + k + 1; j <= n; j++)
if (p[j] - p[i] > max)
max = p[j] - p[i];
cout << max << endl;
delete[] p;
}
Более эффективное решение основано на понимании, что максимальную сумму можно получить, когда префиксная сумма конечного элемента, как можно больше, а префиксная сумма предшествующая начальному элементу, как можно меньше. Однако, недостаточно просто найти максимальную префиксную сумму и предшествующую ей на расстоянии не менее k+1 минимальную сумму или найти минимальную сумму и последующую на нужном расстоянии максимальную, т.к. на исключаемом интервале может существовать значение, которое образует большую разность. Поэтому для каждой вычитаемой суммы находим максимальную уменьшаемую сумму, значение которой нужно будет повторно искать только, когда уже найденное значение попадет в исключаемый интервал.
Python
f = open("27-170b.txt")
n, k = map(int, f.readline().split())
p = [0]
for i in f:
p.append(p[-1] + int(i))
mx = -10 ** 9
mxi = 0
mxp = 0
for i in range(n - k):
if mxi < i + k + 1:
mxi = i + k + 1
mxp = p[mxi]
for j in range(i + k + 2, n + 1):
if p[j] > mxp:
mxi = j
mxp = p[j]
mx = max(mx, mxp - p[i])
print(mx)
PascalABC
var
n, k, max, maxi, maxp, x, i, j: Integer;
p: array [1..166780] of Integer;
f: TEXT;
begin
Assign(f, '27-170b.txt');
Reset(f);
Readln(f, n, k);
p[1] := 0;
for i := 2 to n + 1 do
begin
Readln(f, x);
p[i] := p[i - 1] + x;
end;
max := -1000000000;
maxi := 0;
maxp := 0;
for i := 1 to n - k do
begin
if maxi < i + k + 1 then
begin
maxi := i + k + 1;
maxp := p[maxi];
for j := i + k + 2 to n + 1 do
if p[j] > maxp then
begin
maxi := j;
maxp := p[j];
end;
end;
if maxp - p[i] > max then
max := maxp - p[i];
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("27-170b.txt");
int n, k;
f >> n >> k;
int* p = new int[166780];
p[0] = 0;
for (int i = 1; i <= n + 1; i++)
{
int x;
f >> x;
p[i] = p[i - 1] + x;
}
int max = -1000000000, maxi = max, maxp = 0;
for (int i = 0; i < n - k; i++)
{
if (maxi < i + k + 1)
{
maxi = i + k + 1;
maxp = p[maxi];
for (int j = i + k + 2; j <= n; j++)
if (p[j] > maxp)
{
maxi = j;
maxp = p[j];
}
}
if (maxp - p[i] > max)
max = maxp - p[i];
}
cout << max << endl;
}
Ответ
1261749 127525277