Oranges!

Subtask 1: enumerate every subset of oranges bought by the first person. For each subset of size $K$, directly compute the satisfaction and take the maximum. This takes $O(N2^N)$ time and $O(N)$ space.

Full solution: if the second person bought everything, the satisfaction would be $\sum_{i=1}^N b_i$. Giving orange $i$ to the first person changes it by $$.

Let $c_i=a_i-b_i$. We must choose exactly differences with maximum sum. Sort them in descending order and select the largest . If an unselected value were larger than a selected value, exchanging them would increase the sum. Thus this choice is optimal. Ties may be resolved arbitrarily.

Writing the sorted values as $c_1\geq c_2\geq\cdots\geq c_N$, the answer is

$$\sum_{i=1}^N b_i+\sum_{i=1}^K c_i.$$

Exactly $K$ oranges must be selected, even when some selected differences are negative.

Each case takes $O(N\log N)$ time and $O(N)$ space. The magnitude of the answer and intermediate sums is at most $2\times10^{14}$, and each difference has magnitude at most . Store sums in 64-bit integers.

Solution written by GPT