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