Connection Status:
Competition Arena > RowGame

RowGame

SRM 450 · 2009-10-17 · by Rydberg

SRM 450 · 2009-10-17 · by Rydberg · Dynamic Programming, Greedy, Search
Class Name: RowGame
Return Type: long
Method Name: score
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

The RowGame is a one-player game in which a single piece is moved across a board. The board consists of N squares arranged in a row, numbered 1 through N, from left to right. Each square has an associated value.

Initially, the piece is on square 1, and the current direction is right. On each turn, the player moves zero or more squares in the current direction. The direction is then reversed for the next turn. Scoring works as follows. Initially the player's score is 0. Each time the player moves from square A to square B, the sum of the values of each square between A and B, inclusive, is added to his score. Values can be negative, and the player is never allowed to make a move that will cause his score to drop below zero.

You are given a int[] board, where the i-th element (0-indexed) is the value of square (i+1). Return the maximum score that can be attained if the player is allowed to make at most k moves.

Constraints

  • board will contain between 1 and 50 elements, inclusive.
  • Each element of board will be between -400000000 and 400000000, inclusive.
  • k will be between 1 and 400000000, inclusive.
Examples
0)
{2,-2,4,3,-10}
3
Returns: 21

Move 1: Move to square 4. You receive 2-2+4+3 = 7 points. Move 2: Move to square 3. You receive 3+4 = 7 points. Move 3: Move to square 4. You receive 4+3 = 7 points.

1)
{-6,5}
10
Returns: 0

There is no way to get a non-negative score after the first move, so you should make no moves at all.

2)
{5,-6}
10
Returns: 50

In each move you can stay in square 1 and earn 5 more points.

3)
{10,-100,80}
3
Returns: 30

1. On the first move, you cannot move to either of the other squares because it would cause your score to drop below zero, so you must stay on square 1 and get 10 points. 2. On the second move, your direction changes to left, but since there are no squares to the left of square 1, your only option is to stay on the same square and get 10 more points. 3. Finally, on the last move, your direction changes back to right, and this time, you have two options: stay on square 1 or move to square 3. Moving to square 3 would make you lose 10 points, for a total score of 10, while staying on square 1 would get you 10 points, for a total score of 30. You choose to stay on square 1.

4)
{10,-100,80}
4
Returns: 90

Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RowGame with a public method long long score(vector<int> board, int k) · 143 test cases · 2 s / 256 MB per case

Submitting as anonymous