Жауабы: Максимальная сумма осадков
Ответы для файлов А и B определяются по приложенным входным файлам; сами файлы в предоставленных данных отсутствуют.
У этого задания официального ключа нет, поэтому ответ получен в разборе және кілтпен салыстырылмаған. Нәтижені жаттамас бұрын, өтіңіз выкладки — там видно, откуда взялось каждое число.
Бланкке: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин в течение $T$ мин. Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин, а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Даны два входных файла — файл А и файл B. Каждый файл в первой строке содержит натуральное число $K$ — количество минут, которое должно пройти между двумя передачами показаний, а во второй строке — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В каждой из следующих $N$ строк находится одно целое неотрицательное число, не превышающее $100\,000, обозначающее количество осадков за соответствующую минуту.
Для каждого файла найдите максимальную сумму двух элементов последовательности, номера которых отличаются не менее чем на $K$. Запишите сначала значение для файла А, затем значение для файла B.
Типовой пример: при $K=3$ и последовательности $15, 10, 200, 0, 30$ максимальная сумма равна $45$ — это сумма значений на первой и пятой минутах.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных пар.
Где здесь ошибаются
Проверяют только пары с расстоянием ровно $K$, хотя требуется расстояние не менее $K$.
Для каждого элемента перебирают все допустимые предыдущие элементы, получая сложность $O(N^2)$.
Неверно учитывают индексы и начинают использовать элемент раньше, чем между показаниями проходит $K$ минут.
Путают сумму максимальных элементов с максимальной суммой допустимой пары.