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.
Для отправки решений необходимо выполнить вход.
|