COCI '07 Regional #2 Nikola

Points: 10

Time limit: 0.6s

Memory limit: 32M

Problem type

Against his own will, Nikola has become the main character in a game. The game is played on a row of $N$ ~N~ squares, numbered $1$ ~1~ to $N$ ~N~. Nikola is initially in square $1$ ~1~ and can jump to other squares. Nikola's first jump must be to square $2$ ~2~. Each subsequent jump must satisfy two constraints:

If the jump is in the forward direction, it must be one square longer than the preceding jump.
If the jump is in the backward direction, it must be exactly the same length as the preceding jump.

For example, after the first jump (when on square $2$ ~2~), Nikola can jump back to square $1$ ~1~ or forwards to square $4$ ~4~.

Every time he enters a square, Nikola must pay an entry fee. Nikola's goal is to get from square $1$ ~1~ to square $N$ ~N~ as cheaply as possible. Write a program that determines the smallest total cost for Nikola to get to square $N$ ~N~.

Input Specification

The first line contains the integer $N$ ~N~, $2 \le N \le 1000$ ~2 \le N \le 1000~, the number of squares.

Each of the following $N$ ~N~ lines contains the entry fee for one square, a positive integer less than $500$ ~500~. The entry fees will be given in order for squares $1$ ~1~ to $N$ ~N~.

Output Specification

Output the smallest total cost for Nikola to get to square $N$ ~N~.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

In the first example, after jumping to square $2$ ~2~, Nikola jumps back to square $1$ ~1~. From there he can jump to square $3$ ~3~ and then to $6$ ~6~.

Comments

0

Kirito commented on June 29, 2021, 2:53 p.m.

Note that Nikola does not pay to enter the starting square.

-1

Dan13llljws commented on Jan. 29, 2020, 1:23 a.m.

My code passes with Clang++ but not g++. I tested with official test data and got the correct output but when I use C++11 on dmoj i WA