Show problems as
Classic problem #1383HardArrayGreedySortingHeap (Priority Queue)

Maximum Performance of a Team

Real-world version: Rating a Group of Turbines
Tracked in this browser only
Read Maximum Performance of a Team on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A wind farm owns n turbines. Turbine i produces output[i] units of power and runs at a steadiness of steadiness[i].

A group is any non-empty selection of at most k turbines. Its rating is the total output of the turbines in it multiplied by the smallest steadiness among them.

Return the largest rating a group can reach. Because that number can be large, return it modulo 10^9 + 7.

Examples

Example 1

Input
n = 3, output = [2, 4, 6], steadiness = [8, 5, 3], k = 2
Output
30

The first two turbines total 6 in output with a smallest steadiness of 5, a rating of 30. The last two total 10 with a smallest steadiness of 3, also 30. Nothing does better.

Example 2

Input
n = 2, output = [10, 1], steadiness = [10, 1], k = 2
Output
100

Adding the second turbine lifts the output to 11 but drags the smallest steadiness down to 1, rating 11. The first turbine on its own rates 100, so the best group is smaller than the limit allows.

Example 3

Input
n = 2, output = [10, 1], steadiness = [1, 100], k = 1
Output
100

Only one turbine may be taken. The first rates 10 and the second rates 100.

Constraints

  • 1 <= k <= n <= 10^5
  • output.length == n
  • steadiness.length == n
  • 1 <= output[i] <= 10^5
  • 1 <= steadiness[i] <= 10^8

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_performance(n: int, output: list[int], steadiness: list[int], k: int) -> int:
Java
public int maxPerformance(int n, int[] output, int[] steadiness, int k)

More on the same topics