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
Edit: ok, even using a specialized data structure (Python's deque from collections) I still keep the times of my solution with a module indexed window...
If you have any tip, I'll be glad to follow it and try again a new solution.
Meanwhile, thanks for your kind feed :)
There aren't any special data structures you need. Just a list applied in a particular way. Even still, you might be better off either moving on, or attempting it in a different language.
The judge should have different time limits for different languages.
I'm not 100% sure this will pass though.
I think the judge will give you runtime error if you try that.
That's my two cents.
Test case #1a: OK [0.224s, (memory redacted)] (5/5)