Posted on

Description

Submission

class Solution {
    typedef pair<int, int> PII;
    typedef long long ll;
    const int M = 1e9+7;
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        vector<PII> person;

        for(int i = 0; i < n; ++i) {
            person.push_back({efficiency[i], speed[i]});
        }

        sort(person.begin(), person.end(), greater<>());
        
        ll ret = 0;
        ll sum = 0; // sum of speed
        for(int i = 0; i < n; ++i) {
            auto [e, s] = person[i];
            sum += s;
            pq.push(s);
            while(pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }

            ret = max(ret, sum * e);
        }

        return ret % M;
    }
};

// traverse minimum efficiency

Leave a Reply

Your email address will not be published. Required fields are marked *