Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every contiguous $n$ elements there are at most $k$ chosen.

As this is an old high-school level contest problem, I ask for some hints. Also, this means I know there exists a solution far quicker than the proposed by D.W. and most likely not very complicated, so the question is still open.

My ideas mostly involved dynamic programming. I was trying to calculate, for each prefix of the array, best score we can acquire. However, in order to do this, I think I would need to calculate it for every prefix, and every possible choosing of $k$ numbers in the last $n$ numbers of this prefix, resulting in complexity $O(n^{k+1})$, which is far from acceptable. Also, I thought of looking at pairs of positions in the array which are distant by $n$ and their relation to each other, but this approach fails, as in an optimal solution not in every contiguous $n$ element we would choose exactly $k$, sometimes it could be less.

Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $[1, n], [n+1, 2n] \ldots [(t-1)n+1, tn]$ we can't take more than $k$ elements, so the number of taken elements won't be larger than $t\cdot k$. Let's call the indices of taken elements in the given array $x_1, x_2 \ldots x_{tn}$. It's easy to notice that $x_i + n \le x_{i+k}$, because there can't be more than $k$ elements in any window of size $n$.

With this knowledge we are ready to construct dynamic programming solution, which would choose in parallel indices for every segment $[x_1 \ldots x_k], [x_{k+1} \ldots x_{2k}] \ldots [x_{(t-1)k+1} \ldots x_{tk}]$ separately.

$$dp[k+1][k+1][k+1]...(t\,times)[tn]$$
We would iterate trough positions $i$ from $1$ to $tn$ and every time decide whether we want to take one more element in the first segment from the position $i$, in the second segment from the position $i+n$, in the third segment from the position $i+2n$ etc. Bear in mind that at any point any segment cannot have more chosen elements than one of its preceding segments.

For $t = 3$:
$$dp[a][b][c][i] = max(dp[a][b][c][i-1], dp[a-1][b][c][i-1] + A[i], dp[a][b-1][c][i-1] + A[n + i], dp[a][b][c-1][i-1] + A[2n + i], dp[a-1][b-1][c][i-1] + A[i] + A[n+i] \ldots)$$
There are in total $3^t$ different combinations of taking elements from $i$-th position and it can be easily fixed in code using additional $3^t$ states.
if $a \le b \le c$ is not met:
$$dp[a][b][c][i] = -inf$$

Result of the given task is stored in one of $dp[x][0][0][tn], dp[k][x][0], dp[k][k][x]$ states for any $x$ depending on how many elements does the optimal solution use.

So overall time complexity is $O(tn(k+1)^t3^t)$ and space complexity is $O(tn(k+1)^t)$.

StackExchange Computer Science Q#29898, answer score: 2