The solution of the first subtask is based on dynamic programming where the state is a bitmask. We leave the rest of the details as a practice to the reader.

In the second subtask, it is known that ~R = N~, which means that we can swap numbers on positions ~L, L+1, \dots, R~ only with numbers on positions from ~1~ to ~L-1~ (the rest of the solution assumes that the word interval refers to the agreed interval ~L, L+1, \dots, R~). The first important observation is that we will never change the position of a certain number more than once. The second important observation, and much less obvious than the first, is that we only care about which elements were chosen to be swapped within the interval and which were chosen to be swapped outside the interval. Regardless of the way in which we have swapped these numbers, their total cost will remain invariant. For example, if we decided to swap positions ~i~ and ~j~ from within the interval with positions ~k~ and ~l~ that are outside the interval, it doesn't matter whether we have changed ~i~ with ~k~ and ~j~ with ~l~ or ~i~ with ~l~ and ~j~ with ~k~. We leave the formal proof of this claim as an exercise to the reader.

Now it is obvious that the only important thing left is to decide which elements should be chosen from inside and which elements should be chosen from outside of the interval and that the number of chosen elements from inside equals the number of chosen elements outside of the interval. We can achieve that using ~dp~ whose arguments are the current position outside the interval, current position inside the interval and the total amount of money we have spent thus far. The ~dp~ function returns the maximum decrease in the sum of elements in our interval. The initial state of ~dp~ is ~dp(1, L, 0)~ and the state where we will find our solution is ~dp(L-1, R, K)~.

$$\displaystyle dp(poz_{out}, poz_{in}, spent) = \max\begin{cases} dp(poz_{out}-1, poz_{in}, spent) \\ dp(poz_{out}, poz_{in}-1, spent) \\ dp(poz_{out}-1, poz_{in}-1, spent-(poz_{in}-poz_{out}))+A[poz_{in}]-A[poz_{out}] \end{cases}\tag{1}$$

The first ~dp~ transition tells us not to take an element on position ~poz_{out}~, the second transition tells us not to take an element on position ~poz_{in}~, while the third transition tells us to take both elements and swap them, thus spending ~poz_{in}-poz_{out}~ kunas.

The complexity of this algorithm is ~\mathcal O(N^2 K)~.

This algorithm is therefore fast enough for the whole solution, but doesn't include the swaps from the right side of the interval because ~R = N~. Suppose that the optimal solution takes ~X~ elements left of the interval, ~Y~ elements right of the interval and ~X+Y~ elements from inside the interval. It is obvious that, if we sort positions of elements we took from within the interval, first ~X~ elements will be swapped with the ~X~ chosen elements on the left side and next ~Y~ elements will be swapped with the ~Y~ chosen elements on the right side. This leads us to a conclusion that there is a line between positions within the interval which determines that all elements from the interval left of that line will be swapped with chosen elements left of the interval, and vice versa for the right side. Since we don't know where that line might lie and since we don't actually care how many swaps are made on each side of an interval, we can place that line on each position within the interval. We can do that with the following lines of code:

for i in range (L-1, R+1):
  for j in range (0, K+1):
    sol = max(sol, dpL(L-1, i, j) + dpR(R+1, i+1, K-j))

What are dpL and dpR? dpL is the same ~dp~ from the last subtask and dpR is completely identical to it but is being done from the other side. The complexity of each ~dp~ is ~\mathcal O(N^2 K)~ and the complexity of merging their solutions is ~\mathcal O(NK)~. Therefore, the total complexity of the algorithm is ~\mathcal O(N^2 K)~.

Why can't you score all the points with that solution then? Because a tridimensional array of the form int dp[N][N][K] takes up too much memory for ~N = 100~, but it fits for ~N = 50~. Therefore, we still need to optimize our memory consumption. There are multiple ways to achieve that, but perhaps the easiest is to note that, in the worst case for any ~N~, ~L~ and ~R~, the maximum amount of money Ivica needs to perform all swaps is going to be bounded by ~N^2/4~. Luckily, arrays of the form int dp[N][N][N*N/4] fit into the given memory limit of 256 MiB. There is another optimization which swaps the dimension ~N~ with a smaller constant.