leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0502.cpp (1039B)

      1 class Solution {
      2     typedef pair<int, int> pii;
      3 
      4   public:
      5     int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
      6         vector<pii> data(profits.size());
      7         for (int i = 0; i < profits.size(); i++)
      8             data[i] = {capital[i], profits[i]};
      9         sort(data.begin(), data.end());
     10 
     11         auto cmp = [](const pii &a, const pii &b) { return a.second < b.second; };
     12         priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
     13 
     14         int i = 0;
     15         while (i < profits.size() && k) {
     16             if (data[i].first <= w)
     17                 pq.push(data[i++]);
     18             else {
     19                 while (!pq.empty() && data[i].first > w && k) {
     20                     w += pq.top().second;
     21                     pq.pop();
     22                     k--;
     23                 }
     24                 if (pq.empty() && data[i].first > w) break;
     25             }
     26         }
     27         while (!pq.empty() && k) {
     28             w += pq.top().second;
     29             pq.pop();
     30             k--;
     31         }
     32 
     33         return w;
     34     }
     35 };