Observe that it is never worth it to open a negative valued gift or to turn a positive valued gift into a negative one. Gifts with a value of ~0~ can simply be ignored. Thus, we can consider the move cost of collecting a gift which is initially positive as ~1~ (simply open it) and the move cost of collecting a gift which is initially negative to be ~2~ (flip its sign, then open it). For convenience, we can split the positive and negative gifts into two separate lists. Now, it is also always better to take larger valued gifts before smaller valued gifts. Thus, we sort both the positive and negative lists in decreasing order of absolute value. Denote the sorted list of positive gift values as ~p_i~ and the sorted list of negative gift values as ~n_i~. Let there be ~N_p~ positive gifts and ~N_n~ negative gifts.

From here, there are two THREE main solutions:

Solution 1

Let ~X~ be the number of positive gifts we open. Opening these ~X~ gifts will cost ~X~ moves, leaving us with ~K - X~ moves to open the negative gifts. However, since each negative gift costs ~2~ moves, we can only open at most ~\lfloor \frac{K - X}2 \rfloor~ of them.

Now, we can loop over all possible values of ~X~ from ~1~ to ~\min(K, N_p)~ and consider taking the ~X~ greatest positive gifts and ~Y = \min(\lfloor \frac{K - X}2 \rfloor, N_n)~ greatest negative gifts. The total happiness score for a given value of ~X~ will be

~ \begin{gather*} (p_1 + p_2 + \dots + p_X) - (n_1 + n_2 + \dots + n_Y) \end{gather*} ~

To optimize the calculation of these sums, we can either use prefix sum arrays or accumulate the sum while looping. The final answer is the maximum sum across all possible values of ~X~. A similar solution which instead loops over the number of negative gifts to open will also work. Implementation must be done carefully to ensure indexes are in range.

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

Solution 2

Observe that if ~K~ is odd, it is optimal to immediately use ~1~ move to take the greatest positive valued gift. Any greedy solution which does the following but skips this step will receive a Wrong Answer verdict. (Thanks to Riolku for pointing this out and breaking the original reference solution, and thanks to Snowfall for showing that this solution can be salvaged via this extra step).

We can pair up consecutive items in the sorted positive value list and treat them as having a collective move cost of ~2~. Then, we can greedily choose between either the next greatest negative valued gift or the next greatest pair of positive valued gifts, whichever one gives the maximum total happiness-value. In any case, this will cost ~2~ moves. If there are no more negative valued gifts, then simply spend the remaining moves on the positive valued gifts. If there are no more positive valued gifts, spend the rest of the moves on the negative valued gifts. If there is only one positive gift left, we can simply treat it as being paired with a ~0~. It actually doesn't matter if we take this last positive gift and reduce our move count by ~2~, since all remaining gifts would be negative (costing ~2~ moves), and reducing our move count by ~1~ to an odd number effectively renders one move useless anyway. This can be done with an extra if statement, or by padding the positive list with a zero to ensure it has an even number of elements. Very careful implementation is required for a greedy solution of this type to pass.

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

Solution 3

Similarly to Solution 2, we can compare the next greatest negative gift against the next two greatest positive gifts. However, if the next two greatest positive gifts are greater, we should only take the greatest positive gift, not both of them. This avoids the trouble encountered in Solution 2 and we do not have to check if ~K~ is odd at the beginning. (Thanks to htoshiro for showing me this solution).

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

Bonus

Python golf solution (220 bytes): https://dmoj.ca/src/6867362