OpenFIPI 2.0

27

6

DD9960

undefined

Задание выполняется с использованием прилагаемых
файлов.

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

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

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

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

Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

 

Типовой пример организации данных во входном файле

2

6

150

–150

20

–200

–300

0

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

 

Просмотреть отправленные ответы DD9960

Просмотреть отправленные комментарии DD9960