Two Tasters

Medium

There are n dishes on the table, shared between two tasters so that each dish goes to exactly one of them. If the first taster eats dish i, it earns first[i] points; if the second one does, it earns second[i] points. The first taster must try exactly first_count dishes, and the second takes all the rest. Return the largest possible total score.

Example 1

first=[5, 2, 8, 3], second=[1, 6, 4, 3], first_count=2 → 22

The first taster gets dishes 0 and 2 (5 + 8), the second gets 1 and 3 (6 + 3). Total: 22.

Example 2

first=[4, 4, 4], second=[9, 1, 7], first_count=0 → 17

The first taster gets nothing, so the second takes everything: 9 + 1 + 7 = 17.

Example 3

first=[3, 10], second=[7, 2], first_count=2 → 13

Constraints

1 ≤ n = len(first) = len(second) ≤ 10⁵
1 ≤ first[i], second[i] ≤ 1000
0 ≤ first_count ≤ n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting Heap (Priority Queue)

Similar problems

Studios for Recording Sessions Medium Jobs With a Cooldown Medium Spread Out the Labels Medium Cross Out Half the List Medium One Event per Day Medium

Input

first=[5, 2, 8, 3], second=[1, 6, 4, 3], first_count=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.