1383. Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

class Solution {
public:
    int maxPerformance(int n, vector<int>& sp, vector<int>& ef, int k) {
        long long res = 0, sum = 0, mod = 1e9 + 7;
        vector<pair<int, int>> A;
        priority_queue<int> pq;
        for(int i = 0; i < n; i++)
            A.push_back({ef[i], sp[i]});
        sort(rbegin(A), rend(A));
        
        for(auto& [e, s] : A) {
            sum += s;
            pq.push(-s);
            if(pq.size() > k) {
                sum += pq.top(); pq.pop();
            }
            
            res = max(res, sum * e);
        }
        
        return res % mod;
    }
};