Subtask 1

The first observation to make is that swapping costs is the exact same as swapping values. Furthermore, we can view each swap as a combination of two actions: ignoring the value of one item (i.e. add only its cost) and ignoring the cost of another item (i.e. add only its value). This leads to the dynamic programming state ~dp[n][c][a][b] :=~ the maximum total value attainable from the first ~n~ items with a total cost of ~c~, given that we've ignored the value of ~a~ items and we've ignored the cost of ~b~ items. The transitions are almost identical to those of 0-1 knapsack, and the final answer is the maximum of all states where ~a = b~.

Time Complexity: ~\mathcal{O}(NCK^2)~

Subtask 2

We will first sort the items in increasing order of cost. Now, we realize that all swaps proceed in one direction. That is, we will always ignore the value of an earlier item in exchange for being able to ignore the cost of an item later on. A very simple solution now follows from this observation: if we define our state to be ~dp[n][c][k] :=~ the maximum total value attainable from the first ~n~ items with a total cost of ~c~ given that we've ignored the value of ~k~ items, then the final answer is the maximum of all ~dp[n][c][k] \; +~ the ~k~ largest values from the last ~N-n~ items.

Time Complexity: ~\mathcal{O}(NCK)~

Subtask 3

For full marks, we observe that most of the time it is optimal to use all ~K~ of our swaps. Furthermore, there exists some prefix of length ~l~ in which we take all ~l~ of the costs and the ~l-K~ largest values among them, and there exists some suffix of length ~r~ in which we take the ~K~ largest values among the last ~r~ items. All of the swapping occurs between the prefix and the suffix, so the optimal choices for the middle portion can be computed simply by using normal 0-1 knapsack.

The only time it is better to use less than ~K~ swaps is when we have more than enough swaps to take as many of the smallest costs as possible, and to each of these costs assign the largest possible values. This case should be handled carefully in order to obtain full marks.

Time Complexity: ~\mathcal{O}(NC)~