aboutsummaryrefslogtreecommitdiff
path: root/max_performance_team.cpp
blob: 07a6e6e842e9572481be784c9aba1568c2906dee (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "leetcode.h"

class Solution {
public:
  const int mod = (int)1e9 + 7;
  int maxPerformance(int n, vector<int> &speed, vector<int> &efficiency,
                     int k) {
    priority_queue<int, vector<int>, greater<int>> pqvg;
    vector<pair<int, int>> vp;
    for (int i = 0; i < n; i++)
      vp.push_back({efficiency[i], speed[i]});
    sort(vp.rbegin(), vp.rend());
    long totSpeed = 0, ans = 0;
    for (int i = 0; i < n; i++) {
      int currEff = vp[i].first, currSpeed = vp[i].second;
      if (pqvg.size() == k) {
        totSpeed -= pqvg.top();
        pqvg.pop();
      }
      pqvg.push(currSpeed);
      totSpeed += currSpeed;
      ans = max(ans, totSpeed * currEff);
    }
    return ans % mod;
  }
};

int main() {
  Solution obj;
  int n = 6, k = 2;
  vector<int> speed = {2, 10, 3, 1, 5, 8}, efficiency = {5, 4, 3, 9, 7, 2};
  cout << obj.maxPerformance(n, speed, efficiency, k);
}