CCO '07 P3 - Bowling for Numbers++

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2007 Stage 2, Day 1, Problem 3

Recall that at the Canadian Carnival Competition (CCC), a popular game was Bowling for Numbers. A large number of bowling pins were lined up in a row. Each bowling pin had a number printed on it, which was the score obtained from knocking over that pin. The player was given a number of bowling balls; each bowling ball was wide enough to knock over a few consecutive and adjacent pins.

For example, one possible sequence of pins was:

2 8 5 1 9 6 9 3 2

If Alice was given two balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would be 39, the sum of two throws: 2+8+5 = 15, and 9+6+9 = 24.

Since many, including you, have mastered the art of throwing balls at pins, the old and wise members of the Canadian Carnival Competition Committee have decided to make the game slightly more difficult by introducing the concept of penalty pins.

Penalty pins are pins with a negative score, such that a player's score decreases when they are knocked over. This can change the player's strategy, as the player can use the empty spaces to the left and right of the pins, as well as spaces created by previous throws, to avoid hitting penalty pins. Consider the following example:

2 8 -5 3 5 8 4 8 -6

If Alice was given three balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would be 38, the sum of three throws: 2 + 8, 3 + 5 + 8, and 4 + 8. Alice's first throw is deliberately to the left and catches only the leftmost two pins, avoiding the -5. Alice's second throw hits 3 5 8, and her third throw catches the remaining 4 8, going through the space created by her second throw to avoid the -6.

Bob has a strategy where he picks the shot that gives him the most score, then repeatedly picks the shot that gives him the most score from the remaining pins. This strategy doesn't always yield the maximum score, but is close. On the test data, such a strategy would get a score of 20%.

Input Specification

Input consists of a series of test cases. The first line of input is t, 1 \le t \le 10, indicating the number of test cases.

The first line of each test case contains three integers. First is the integer n, 1 \le n \le 10\,000, indicating the number of bowling pins. The second integer, k, 1 \le k \le 500, giving the number of bowling balls available to each player. The third and final integer is w, 1 \le w \le 100, the width of the bowling ball (the number of adjacent pins it can knock over).

The next n lines of each test case each contain a single integer giving the score of the pins, in order. The scores are in the range -10\,000 \dots 10\,000 inclusive.

20% of the test data will have size n \le 50.

Output Specification

For each test case, output the maximum achievable score by the player. This score is guaranteed to be less than one billion.

Sample Input

2
9 2 3
2
8
5
1
9
6
9
3
2
9 3 3
2
8
-5
3
5
8
4
8
-6

Sample Output

39
38

Comments


  • 0
    maxcruickshanks  commented on Feb. 27, 2022, 2:22 a.m.

    Since the original data were weak, an additional test case was added.


  • 14
    sunnylancoder  commented on Jan. 5, 2018, 3:39 a.m.

    Can the throw not hit any pins at all?


    • 9
      Aaeria  commented on Nov. 25, 2019, 3:35 p.m.

      Yes