The Heist

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are planning a heist on one of the worst museums in the world. You've already planned out the entrance and exit routes (consisting of simply walking in and then walking out), so the only task left is to decide which artifacts to bring home. Specifically, the N artifacts of the museum are numbered from 1 to N, laid out in a circular hallway so that the i^{th} artifact is adjacent to the (i+1)^{th} for 1 \le i < N, and the N^{th} artifact is adjacent to the first. The i^{th} artifact has a value of V_i, but being one of the worst museums in the world, V_i could even be negative for some artifacts! Also, if you take more than K items in a row, the emergency alarm will be set off and the doors locked, leaving you soon in the hands of the authorities. Given the circumstances, write a program to help you calculate the maximum net value of artifacts you could take from the museum without setting off the alarm. To ensure the integrity of your solution, there may be multiple test cases.

Input Specification

The first line contains an integer T, the number of test cases.

The first line of each case contains 2 integers N and K, as described in the statement.

The second line of each case contains N integers V_i (1 \le i \le N), the value of the i^{th} artifact.

Output Specification

Output T lines, each containing the answer to the corresponding test case.


For this problem, you will NOT be required to pass the sample case in order to receive points. In addition, you do not have to pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le T \le 10^4

2 \le N \le 10^5

1 \le K \le \min(N, 30)

-10^9 \le V_i \le 10^9

The sum of N over all test cases will not exceed 10^5.

Subtask 1 [15%]

The sum of N over all test cases will not exceed 20.

Subtask 2 [25%]

V_N = -10^9

Subtask 3 [60%]

No further constraints.

Sample Input

5 2
3 1 0 4 5
2 1
-1 -2
4 4
6 1 3 3
9 3
-3 7 -6 1 1 4 2 3 2

Sample Output



The diagram above illustrates the optimal solution to the first case, with the chosen artifacts marked in yellow. Note that it is not allowed to choose the artifacts with values 3, 5, and 4 together, since that is more than 2 chosen artifacts in a row.

In the second case, it is optimal to take nothing at all. (and maybe find a better museum...)

In the third case, it is optimal to take all 4 artifacts.

The optimal solution to the fourth case is illustrated below, with the chosen artifacts marked in yellow.


There are no comments at the moment.