Home
IOI 2011

      Honorary Patron
      Welcome
      Organizers
      Sponsors
      Logo
      IOI Committee

Competition

      Call For Tasks
      Contest Environment
      Practice Tasks
      Rules
      Tasks
      Results
General Information
Registration

      Registration System

Visa Information
Gallery

      Album

Location

      Competition Site
      Room & Function

Press Room

      Newsletter

Sawasdee Thailand

      About Thailand
      Tourist info
      Practical Info
      Talk Thai
      Thai Food
      Shopping Center
      Transportation

Schedule

      Detailed Schedule
      Conference Schedule

IOI TV Program
Contact
TH | EN

Hottest

IOI 2011 | Practice task


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.

Your task

You are to implement procedure maxk(N,T,K) that returns the maximum sum of temperatures of any K consecutive days, where N is the number of days and T is an array of positive integers where T[i], for 0 <= i < N, is the temperature of day i.

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, procedure maxk should return 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

Implementation details

  • Use the RunC programming and test environment. (See the contest environment information here)
  • Implementation folder: hottest/ (download prototype here)
  • To be implemented by contestant: hottest.c or hottest.cpp or hottest.pas
  • Contestant interface: hottest.h or hottest.pas
  • Grader interface: none
  • Sample grader: grader.c or grader.cpp or grader.pas
  • Sample grader input: grader.in.1, grader.in.2, ...
    Note: the sample grader reads N, K, and Ti's, and the expected solution from standard input.
  • Expected output for sample grader input: grader.expect.1, grader.expect.2, ...
  • Compile and run (command line): runc grader.c or runc grader.cpp or runc g rader.pas
  • Compile and run (gedit plugin): Control-R, while editing any implementation or grader file.
  • CPU time limit: 2 seconds
  • Memory limit: 256 MB