e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Метеонаблюдения

prb3869 Алексей учится в пятом классе и собирается стать метеорологом. Недавно он завел дневник, в который занес ежедневные измерения температуры в родном городе. Алексей нашел архивные данные за последние несколько сотен лет, а это означает, что данных у него очень и очень много. Программировать он не умеет и просит Вас написать программу, которая вычисляет среднюю температуру за k последовательных дней, причем такие значения ему нужны за весь период наблюдений:

  • Средняя температура с 1 по k-ый день
  • Средняя температура со 2 по (k + 1) -ый день
  • И так далее, пока есть данные.

А после этого из всех вычисленных значений Алексею нужны только два числа - минимальные и максимальные значения. Помогите Алексею и напишите для него эту программу.

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

В первой строке содержатся два целых числа n и k - количество измерений температуры и количество дней для вычисления средней температуры (1kn105). В следующей строке содержится n целых чисел - данные измерений температуры. Каждое из этих чисел находится в интервале (-100, 100).

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

Вывести две строки, которые содержат минимальную и максимальную среднюю температуру, вычисленную на отрезках длины k. Число округлите до ближайшего целого.

Лимит времени 1 секунда
Лимит использования памяти 122.49 MiB
Входные данные #1
4 2
10 12 18 16
Выходные данные #1
11
17
Источник Задачи отборочного тура Всероссийской командной олимпиады школьников 2011/2012 учебный год