SP17303 BOARD1 - Board

Consider a board with fields numbered from 0 to _n_. On each field _i_ ∈ {1, ..., _n_} there is an integer (possibly negative) number _a_ $ _{i} $ ∈ ℤ. A player is given a pawn on field number 0. Player can move the pawn back and front on distance not exceeding _k_. A pawn can visit all the fields many 0 and _n_ many times, but it can stop moving definitively only at position _n_ (player decides on when to stop). Whenever a pawn visits field _i_, the field is cleared and the number _a_ $ _{i} $ is removed (if the field wasn’t clear before the move). A player wants to maximize the sum of numbers on non-cleared fields. Write a program that reads on the standard input the description of a game, and writes on standard output the value of an optimal strategy. On the first line of input you are given the number _n_ (1 n ). On the second line of input you are given the parameter _k_ (1 k n). In the next _n_ − 1 lines of the input you are given single integer numbers, where on line _i_ + 2 you are given the number _a_ $ _{i} $ . There are no values given for fields 0 and _n_, because these positions will be always clear at the end of the game.

N/A

N/A