CCC '07 S5 - Bowling for Numbers - DMOJ: Modern Online Judge

CCC '07 S5 - Bowling for Numbers

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2007 Stage 1, Senior #5

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

For example, one possible sequence of pins is: 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$ $39$ , the sum of two throws: $2 + 8 + 5 = 15$ $2 + 8 + 5 = 15$ , and $9 + 6 + 9 = 24$ $9 + 6 + 9 = 24$ .

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 it 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$ $t$ , $1 \le t \le 10$ $1 \leq t \leq 10$ , indicating the number of test cases in the file. The first line of each test case contains three integers n k w. First is the integer $n$ $n$ , $1 \le n \le 30\,000$ $1 \leq n \leq 30 000$ , indicating the number of bowling pins. The second integer, $k$ $k$ , $1 \le k \le 500$ $1 \leq k \leq 500$ , giving the number of bowling balls available to each player. The third and final integer is $w$ $w$ , $1 \le w \le n$ $1 \leq w \leq n$ , the width of the bowling ball (the number of adjacent pins it can knock over). The next $n$ $n$ lines of each test case each contain a single non-negative integer less than $10\,000$ $10 000$ , giving the score of the pins, in order. 20% of the test data will have size $n \le 50$ $n \leq 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

Copy

Output for Sample Input

Copy

Comments

0

aqtsaqts commented on Dec. 22, 2022, 2:56 a.m.

Are you able to knock down less pins than the width of the bowling ball?

24

defectivezuckerbot69 commented on Nov. 4, 2018, 5:02 p.m.

if, say, the sequence of pins is 1 2 3 4 5 6 7 8 9, and the width of the ball is 3, if I were to knock down 5 6 7, would I be able to then knock down 4 8 9, or would the space restrict me from doing so?

15

Relativity commented on Nov. 5, 2018, 2:34 p.m.

The space would restrict you from doing so.