Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ibrahim Mesecan.
Jumping frog
Question:
A frog is trying to jump out of stone well. It has some
energy cells or obstacles (positive or negative energy)
on the wall. While passing through the steps (cells), it
takes the energy in that step. It starts from the beginning
and it can either jump over the obstacles or walk forward.
Negative numbers mean jump backward, and positive
numbers mean jump forward. The number in the cell is
the number of cells to jump. For example, if a cell has
1, it means, the from either walk forward or jump over the
next cell. Find out the maximum energy collected (sum of
the energy in the cells visited) when walking
through the cells.
Input specification:
First, you will be given an integer, the height of the well (n).
Then, in the following line you will be given n numbers
(integers from -50 to 50) where 1 ≤ n ≤ 50.
Output specification:
Show one integer: the maximum energy collected.
Sample Input I
8
-2 1 -3 3 -1 -3 3 2
|
Sample Output I
4
|
Sample Input II
8
2 2 -3 -1 5 2 0 -2
|
Sample Output II
11
|
Sample Input III
8
3 -3 2 -3 -1 2 1 -3
|
Sample Output III
7
|
Sample Input IV
3
1 -2 2
|
Sample Output IV
3
|
Explanation:
You can visit every cell only once.
The target is to start from the beginning and to reach to
the right end with the maximum possible value.
When passing from any cell, you can directly go to the right
or you can jump the cell according to the value of the cell.
If the cell value is 2 you jump the following 2 cells. If the
cell value is -2 then you jump 2 cells towards left.
Sample Input 1: If it walks
over the cells, (-2) + 1 + (-3)...3+2 =0 .
If it goes -2, 1, -3 and jumps from
3 to 2 it can have 1. If it goes over -2 and
jumps from 1 and 3, it can have 4. So the max is 4.
Sample Input 2: It can walk through 2, and then
jumps from the second 2 to 5. Then it
jumps again from 2 to out of the path
(2+2+5+2=11) .
Для отправки решений необходимо выполнить вход.
|