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.