# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Yaswanth Phani Kommineni

Tester: Felipe Mota, Aryan

Editorialist: Pratiyush Mishra

# DIFFICULTY:

3213

# PREREQUISITES:

None

# PROBLEM:

You are given three arrays A, B, and C, all of length N. You also have two integers k_1 and k_2.

For every index 1 \leq i \leq N, you must choose **exactly one** of A_i, B_i, or C_i. Find the **maximum** possible sum of chosen elements, such that:

- At most k_1 elements are picked from A, and
- At most k_2 elements are picked from B

# EXPLANATION:

Here to solve this we will first replace A[i] with max(A[i]-C[i],0) and B[i] with max(B[i]-C[i],0) and add all the values in C to the current answer.

We will then take indices of k_1 largest elements in A, add all those values to the current answer and insert all the values of (B[i]-A[i]) (where i is an index of one of the k_1 largest values in a) into a multiset ‘s’. Let’s denote ‘rem’ as an array containing all the remaining indices. We now create two sets (set of pairs) ‘sa’ and ‘sb’ where sa contains all A[i] and i combined, sb contains all B[i] and i combined for all i belongs to rem. Now we add k_2 elements from B greedily. Let Smax be the maximum value in s and SAmax be the maximum value in sa and SBmax be the maximum value in sb,

- if SAmax+Smax >= SBmax we remove Smax from s, SAmax from sa, add (SAmax+Smax) to the current answer, add B[i] - A[i] to s, and remove B[i] from sb where i is the index of SAmax.
- If SBmax > SAmax + Smax, we add SBmax to the current answer, remove SBmax from sb and remove A[i] from sa where i is the index of SBmax.

We do this operation k2 times to get our final answer.

# TIME COMPLEXITY:

O(NlogN) for each test case.