Subtask 1

In this editorial, let us refer to training a person and increment their skill level as a 'move'.

Let ~S~ denote the sum of skill levels of all pairs at any point in time. Our aim is to maximise ~S~.

First, let's say that we have already chosen which people we will train, so we know the final skill level of each person. How can we determine the optimal pairing of the players? Applying the rearrangement inequality, we can see that ~S~ is maximised when we pair the most skilled man with the most skilled woman, the second most skilled man with the second most skilled woman, and so on. This is sufficient to solve subtask 1.

Time complexity: ~\mathcal{O}(N \log N)~

Subtask 2

Note that the order of our moves doesn't matter. Let's say that we have already paired the men and women optimally, and we have already chosen the final skill levels of all the men - all that's left is to allocate the remaining minutes to the women. Every time we train a woman, ~S~ increases by the skill level of that woman's partner. Hence, an optimal solution would be to allocate all remaining moves to the partner of the most skilled man.

By symmetry, if the skill levels of all of the women have been determined, and the remaining moves need to be allocated to the men, it would be optimal to allocate all remaining moves to the partner of the most skilled woman. Combining these observations, we see that there always exists an optimal solution where we only train the man with the highest initial skill level, and the woman with the highest initial skill level. (This also relies on the fact that if we only train the most skilled man, then that man will always remain the most skilled man, with the same being true for the women.)

Therefore, we have reduced the original problem to the following problem:

Given two sequences initially sorted in descending order, ~a_1, a_2, \dots, a_N~ and ~b_1, b_2, \dots, b_N~, performing ~K~ operations incrementing either ~a_1~ or ~b_1~ to maximise the value of ~S = \sum_{i=1}^N a_i b_i = a_1 \times b_1 + a_2 \times b_2 + \dots + a_N \times b_N~.

As ~a_2, a_3, \dots, a_N~ and ~b_2, b_3, \dots, b_N~ are never modified, ~\sum_{i=2}^N a_i b_i~ is never changed. Thus, we only need to maximise the value of ~a_1 \times b_1~ after performing ~K~ total increments. All that remains is to determine how many times to increment ~a_1~ and how many times to increment ~b_1~.

For subtask 2, since ~K~ is small, we can brute force over how many times to increment ~a_1~, with the remaining moves being used to increment ~b_1~.

Time complexity: ~\mathcal{O}(N \log N + K)~

Subtask 3

Whenever we increment ~a_1~, we also increase ~S~ by ~b_1~. Similarly, whenever we increment ~b_1~, we also increase ~S~ by ~a_1~.

To maximise ~S~ after ~1~ move, we should therefore increment whichever of ~a_1~ or ~b_1~ is lowest. It's not too hard to see that the greedy strategy to always increment whichever of ~a_1~ or ~b_1~ is lowest also maximises ~S~ in the long run (try to prove it yourself)!

We can't explicitly simulate performing each move one at a time, so we will instead rely on casework.

Without loss of generality, we can assume ~a_1 \le b_1~ (if not, we can just switch them around). There are two cases:

1. If ~a_1 + K \le b_1~, then we perform all our moves incrementing ~a_1~.
2. Otherwise, increment ~a_1~ by ~(b_1 - a_1)~ so that ~a_1 = b_1~. Then, we can perform half of the remaining moves incrementing ~a_1~ (rounding up or down if necessary), and the rest of the moves incrementing ~b_1~.

Time complexity: ~\mathcal{O}(N \log N)~