favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic Programming - Linear


prb3869 Alex is studying in the fifth grade and is going to be a meteorologist. Alex recently started a diary, where he wrote the daily temperature in his own town. Alex found the historical data for the past several hundred years, which means that he has a lot of data. Alex asks you to write a program that calculates the average temperature during k consecutive days, and he needs these values for the entire observation period:

  • Average temperature from 1-st till k-th day
  • Average temperature from 2-nd till (k + 1)-th day
  • and so on until he has data.

And after all these calculated values Alex needs only two numbers - the minimum and maximum values. Help Alex and write the program for him.


First line contains two integers n and k - the number of temperature measurements and the number of days to calculate the average temperature (1kn105). Next line contains n integers - the temperature measurements. Each of these numbers is in the range (-100, 100).


Print two lines that contains minimum and maximum average temperature, calculated on segments of size k. Round the answer to the nearest integer.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 2
10 12 18 14
Output example #1
Source Задачи отборочного тура Всероссийской командной олимпиады школьников 2011/2012 учебный год