IOI '11 - Pattaya, Thailand
Thailand is a tropical country. Thai people usually say that Thailand has 3 seasons: Hot Summer, Hotter Summer, and Hottest Summer. It especially feels very hot when you have many consecutive days with high temperatures.
You are planning a K-day trip to Thailand. Since you would like to experience the real Thai Summer, you want your stay to be as hot as possible.
You are given a list of forecasted temperatures of N consecutive days. You would like to find the maximum sum of temperatures of K consecutive days. It is guaranteed that 1 ≤ K ≤ N.
Given an array T of N positive integers where T[i], for 0 ≤ i < N, is the temperature of day i, you are to write a program that finds the maximum sum of temperatures of any K consecutive days.
Suppose that N = 6, K = 3 and T = 10 50 30 20 5 1.
There are 4 possible 3-day trips, starting from day 0, day 1, day 2, and day 3; and their sum of temperatures are 90, 100, 55, and 26. Therefore, you should output 100.
The first line will contain the two integers N and K. The next N lines contain the array T, one integer per line.
One integer, the maximum sum of temperatures of any K consecutive days.
6 3 10 50 30 20 5 1
Subtask 1 (50 points)
N ≤ 1 000, 0 < T[i] ≤ 1 000
Subtask 2 (50 points)
N ≤ 1 000 000, 0 < T[i] ≤ 1 000
Point Value: 5
Time Limit: 0.50s
Memory Limit: 16M
Added: Apr 17, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3