The Slowest Sets the Squad's Pace

Hard

There are n candidates for a squad. Candidate i has skill skill[i] and endurance endurance[i]. Pick a squad of **at most** max_size different candidates (at least one). The squad's output is the sum of its members' skills multiplied by the lowest endurance among them. Return the largest possible output. Since it can be very large, return it modulo 10⁹ + 7 (maximise the output itself, not the remainder).

Example 1

n=4, skill=[3, 8, 2, 6], endurance=[6, 2, 9, 4], max_size=2 → 36

Members 0 and 3 give (3 + 6) · min(6, 4) = 36. The most skilled member, 1, drags endurance down: any squad with them makes at most (8 + 6) · 2 = 28.

Example 2

n=3, skill=[5, 5, 5], endurance=[3, 3, 3], max_size=3 → 45

Take everyone: (5 + 5 + 5) · 3 = 45.

Example 3

n=3, skill=[1, 1, 10], endurance=[100, 100, 1], max_size=3 → 200

Members 0 and 1 alone give 2 · 100 = 200: taking everyone is not always better.

Constraints

1 ≤ max_size ≤ n ≤ 10⁵
len(skill) == len(endurance) == n
1 ≤ skill[i] ≤ 10⁵
1 ≤ endurance[i] ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting Heap (Priority Queue)

Similar problems

Growing Capital Project by Project Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Crew Paid by Skill Hard Score Spread of Parcel Groups Hard

Input

n=4, skill=[3, 8, 2, 6], endurance=[6, 2, 9, 4], max_size=2

Expected

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