Many of you may find this very standard. We can sort the array and take the $$$k$$$ largest elements.

This is another standard problem. Since $$$k_1 + k_2 = n$$$, we can think of this problem as assigning everything to array $$$a$$$ and picking $$$k_2$$$ elements to switch over to array $$$b$$$. Specifically, we take $$$\sum_{i=1}^n a_i$$$ and pick subset of $$$k_2$$$ elements that maximizes $$$\sum b_i - a_i$$$, which reduces to P1.

Note that this version doesn't contain the $$$k_1 + k_2 = n$$$ condition, so we have to make another observation.

Observation: if we sort the indices so that $$$a_i$$$ is non-increasing ($$$a_1\geq a_2\geq \dots\geq a_n$$$), in an optimal assignment, there exists a position $$$p$$$ where all (1) $$$i=[1, 2, \dots, p]$$$ is either in $$$S$$$ or $$$T$$$, and (2) a subset of $$$[p+1, \dots, n]$$$ is part of $$$T$$$.

Proof: we can let $$$p = \max(S)$$$. If there are any $$$i=[1, 2, \dots, p]$$$ where it's not part of $$$S$$$ or $$$T$$$, then the assignment isn't optimal: we can exchange that for $$$p$$$, which achieves a higher sum since $$$a$$$ is non-increasing.

For the solution, we can enumerate $$$p$$$. We know we want exactly $$$k_1$$$ in each prefix assigned to $$$S$$$, the rest of the prefix assigned to $$$T$$$, and $$$k_2 - (p - k_1)$$$ elements of the suffix assigned to $$$T$$$. This nicely reduces to P2 and P1 respectively. To simulate adding/removing elements and finding the sum of the $$$k$$$ largest numbers, we can use a data-structure such as a priority queue or a Fenwick Tree.

The solution runs in $$$O(n\log n)$$$.

Note that we should only perform the operations on the $$$x$$$ largest elements for some $$$x$$$. Also, if we're performing both operations on a single integer, it's always better to subtract before halving. Try to come up with a $$$O(n^2\log n)$$$ solution.

A $$$O(n\log n)$$$ solution also exists.

The editorial nicely proves why it's optimal to perform both operations to the $$$p$$$ largest elements.

Out of $$$k$$$ states, we want to choose $$$t$$$ collaborators and $$$k-t$$$ votes.

Note that we should spend time getting $$$t$$$ collaborators before getting the remaining votes. Additionally, for the collaborators, we should deliver speeches in order of non-decreasing order of $$$b_i$$$.

Let's order the states by increasing order of $$$b_i$$$.

Let's enumerate $$$t$$$, the number of collaborators we get.

Let's order the states by increasing order of $$$b_i$$$. We can prove we will spend at least $$$a_i$$$ hours for a prefix $$$p$$$ and spend exactly $$$a_i$$$ hours getting votes for some states of the suffix. I'll leave the proof as an exercise for the reader. (Hint: it's similar to the analysis of P3.)

Using this, let $$$\text{dp}[i][j]$$$ represent the minimum time in the first $$$i$$$ states to get $$$j$$$ collaborators and $$$i-j$$$ votes. For transitions, we can consider two cases: spending $$$a_i$$$ or $$$b_i$$$ hours. Specifically, we have $$$\text{dp}[i][j] = \min(\text{dp}[i - 1][j] + \frac{a_i}{t+1}, \text{dp}[i - 1][j - 1] + \frac{b_i}{j})$$$. For the first case, we'll have $$$t+1$$$ people (Rie and $$$t$$$ collaborators). For the second case, we'll have $$$j$$$ people (Rie and the $$$j-1$$$ collaborators before getting the $$$j$$$-th).

Now, for a prefix $$$p$$$ we'll have $$$p$$$ votes and we need $$$k-p$$$ more. Note that it's optimal to pick the $$$k-p$$$ smallest $$$a_i$$$ in the suffix, which can be done by precomputing in $$$O(n^2)$$$. Let the set of picked indices in the suffix be $$$S$$$. Afterwards, for each $$$t$$$ and $$$p$$$, we'll update our answer with $$$\text{dp}[p][t] + \sum_{i\in S} \frac{a_i}{t+1}$$$.

The time complexity is $$$O(n^3)$$$.

Code