HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


2013-12-50. 50674 - Collecting Eggs

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2013-04-80. 50343 - The number of...
• 2013-04-90. 50332 - Variance of a ...
• 2013-05-10. 50552 - Casual shoes
• 2013-05-30. 50580 - Days passed
• 2013-05-40. 50553 - Divisible by m
• 2013-05-50. 50593 - Transporter
• 2013-12-10. 50352 - Selling Cows
• 2013-12-40. 50342 - 100 Factorial
• 2013-12-50. 50674 - Collecting ...
• 2013-Nov-01. 50328 - How far away
• 2013-Nov-02. 50347 - Selling Oranges
• 2013-Nov-05. 50354 - Intersecting ...

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Osman Ay.

Collecting Eggs

Farmer George has a chicken farm. The chickens live in a hen house. There are N nesting-boxes where the chickens lay their eggs. These nesting-boxes are numbered from 1 to N consecutively. The Kth nesting-box is neighboring with K-1th and K+1th nesting-boxes.

The chickens lay their eggs in any of the nesting-boxes. Thus, each morning there can be different numbers of eggs in the boxes, and some boxes can be empty.

Farmer George uses a robot to collect the eggs in the nesting-boxes. The robot collects the eggs every morning and it has been programmed as follows:

  • It enters a box only once and picks all the eggs there.
  • When it takes the eggs from a box, it takes the eggs from two neigbouring nesting-boxes.
  • When the eggs from two consecutive boxes have been taken, the next one must be skipped.
  • It can skip as many boxes as it wishes.

Question:
To help farmer George, write a program that calculates the maximum number of eggs that can be gathered by the robot.

Input specification
The first line of the input has an integer N (2 ≤ N ≤ 2500) representing the number of the nesting-boxes. In the second line, there are N integers (each in the 0..100 range) representing number of the eggs in the nesting-boxes. The first number is for the first nesting-box, the second one is for the second nesting-box, and so on. The numbers in the second line are separated by a space.

Output specification
Show just one integer number: maximum number of eggs that can be gathered by the robot.

Sample Input I   
10
3 4 0 1 0 6 7 1 2 1
Sample Output I   
23

Explanation: (3+4) + (6+7) + (2+1) = 23

Time Limit: 0.1 second /test.


Для отправки решений необходимо выполнить вход.

www.contester.ru