 # ARR3 Editorial

Setter: Yaswanth Phani Kommineni
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra

3213

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.

1 Like