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 ai ∈ Z. 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 ai 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.
Input
On the first line of input you are given the number n (1 ≤ n ≤ 1000). 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 ai. There are no values given for fields 0 and n, because these positions will be always clear at the end of the game.Output
A single integer giving the required answer on a separate line for each test case.
Example
Input: 5 5 15 5 8 15 Output: 43
Input: 5 2 15 5 8 15 Output: 30
hide comments
hodobox:
2016-07-04 16:31:54
very concisely: Given fields 0,1,2...N, choose a subset of fields so that from any field the nearest chosen field to the right is at most K units away, such that the sum of all not chosen fields is maximum possible. |
|
Vamsi Krishna Avula:
2014-12-29 11:58:03
I think the problem statement is not explicit, so here goes my version:
|
|
Samuel Nacache:
2014-03-15 19:48:45
Can someone explain second case? If he can't move exceeding 2, can't he move one by one? |
|
Rishabh Sharma:
2013-12-29 13:16:25
Someone please explain the question. The language is very confusing. What does "A pawn can visit all the fields many 0 and n many times" mean?
|
|
Goldie:
2013-12-11 16:47:14
Be careful with negative numbers. Last edit: 2013-12-29 19:42:12 |
Added by: | Marek Adamczyk |
Date: | 2013-11-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |