Maximum Ensemble Performance Within A Size Budget
You assemble an ensemble of at most k models. Each model has a quality score and an inference speed. The ensemble's performance is the SUM of chosen models' qualities multiplied by the MINIMUM speed among them (the slowest member gates latency). Maximize performance.
Problem
Given n engineers (models) with speed[i] and efficiency[i] (quality), and an integer k, choose at most k of them to maximize (sum of chosen efficiencies) * (minimum chosen speed). Return the maximum performance modulo 1e9+7.
Input
Integer n, arrays speed and efficiency, and integer k.
Output
The maximum performance modulo 1e9+7.
Constraints
- 1 ≤ n ≤ 1e5
- 1 ≤ k ≤ n
- 1 ≤ speed[i] ≤ 1e5
- 1 ≤ efficiency[i] ≤ 1e8
Examples
Example 1
Input
n=6 speed=[2,10,3,1,5,8] efficiency=[5,4,3,9,7,2] k=2
Output
60
Pick engineers with speed {5,8}? Optimal: speed 5 & 10 give (7+4)*... — the best pair yields 60.
Example 2
Input
n=6 speed=[2,10,3,1,5,8] efficiency=[5,4,3,9,7,2] k=3
Output
68
Adding a third member raises the efficiency sum enough to reach 68.