IOI '11 - Pattaya, Thailand

Hottest

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.

Example

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.

Input Format

The first line will contain the two integers N and K. The next N lines contain the array T, one integer per line.

Output Format

One integer, the maximum sum of temperatures of any K consecutive days.

Sample Input

6 3
10
50
30
20
5
1

Sample Output

100

Subtasks

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

All Submissions
Best Solutions

Point Value: 5
Time Limit: 0.50s
Memory Limit: 16M
Added: Apr 17, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

[user] is hardcoding for the test case, I was wondering if it is against the rules in any way?

Yes. I've removed the offending submissions.

Just asking, as I'm at a loss about how to implement it and still stay in the time limit. I may try looking for some FIFO data structure and improve it a bit more, but I am not sure that I can halve the times, mh...

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...

It appears that the memory limit is too low to even read all the input into a list. AFAIK, this is impossible to solve with python without buffering the input.

No idea how to implement that, though, as even trying with other data structures, as I stated, I seem to fail.

If you have any tip, I'll be glad to follow it and try again a new solution.

Meanwhile, thanks for your kind feed :)

After having wasted an hour on it, I can confirm that doing this in Python is, at least, quite difficult.

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.

Just to be sure: did you succeed in doing it with P3 or it was a totally wasted effort (apart from practicing, of course) even on your side?

The best I managed to get was the entire first batch case, plus one sub-case of the second batch. On a 5 point, non-partial problem that's fairly easy in C, I'd say it was mostly a wasted effort :)

I was only able to get the same as sigkill in Python 3.(first batch and first of second batch)
The judge should have different time limits for different languages.

Try
[code]
    import sys
    all_data = sys.stdin.read().split('\n')
[/code]
I'm not 100% sure this will pass though.

EDIT:
I think the judge will give you runtime error if you try that.

 
    import sys 
    all_data = sys.stdin.read().split('\n') 

Data too large.

I haven't managed to solve this in Python 2, even though I used basically all possible tricks. Despite getting the data to fit into memory for the second last case, it still times out. I say this is worth way more than 5 points if someone solves it in python.

I have to agree with xiaowuc1; even with the 0.5 second limit, my linear-time, cache-friendly algorithm timed out on the last two cases when implemented in Java.  I had to dust off my ancient C manual to get it to pass all the tests, and even then the last two cases ran over 0.1 seconds.
That's my two cents.

Your Java solution had quite a lot of constant overhead (mod is expensive), not to mention you were using Scanner.

Thanks for your reply, Eagle; I always use Scanner, but a quick Google search suggested that some combination of BufferedReader, InputStreamReader and Integer.parseInt is better.  Is this what you would recommend to read the data faster?

I made the optimizations you suggested, and it indeed runs in under 0.2 seconds now in every case.  Thanks again.

I think the 0.10 second time limit on this problem is unreasonable. 0.10 seconds isn't enough time to even read in the entire input file in some languages. The actual time limit in the practice environment appears to be [url=http://www.ioi2011.or.th/practice-task2]2 seconds[/url], for reference.

the time limit is 0.5 seconds. and you solved the problem so why does it matter?

The time limit was 0.1 seconds, and my solutions originally had TLE prior to the rejudging. Asymptotically though, I'm confident that they have the same time complexity as the intended solution.

Test case #1a: OK [0.224s, (memory redacted)] (5/5)