leetcode

commit 257b78260e9fdf450bb2f02d82353a36961d6778
parent 9e15dcefeca18cc159971a77fcfa0cf6fbe824df
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 23 Feb 2023 11:08:43 +0100

Daily Problem

Diffstat:
A
Problems/0502.cpp
 | 
35
+++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/0502.cpp b/Problems/0502.cpp
@@ -0,0 +1,35 @@
+class Solution {
+  typedef pair<int, int> pii;
+
+public:
+  int findMaximizedCapital(int k, int w, vector<int> &profits,
+                           vector<int> &capital) {
+    vector<pii> data(profits.size());
+    for (int i = 0; i < profits.size(); i++) data[i] = {capital[i], profits[i]};
+    sort(data.begin(), data.end());
+
+    auto cmp = [](const pii &a, const pii &b) { return a.second < b.second; };
+    priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
+
+    int i = 0;
+    while (i < profits.size() && k) {
+      if (data[i].first <= w)
+        pq.push(data[i++]);
+      else {
+        while (!pq.empty() && data[i].first > w && k) {
+          w += pq.top().second;
+          pq.pop();
+          k--;
+        }
+        if (pq.empty() && data[i].first > w) break;
+      }
+    }
+    while (!pq.empty() && k) {
+      w += pq.top().second;
+      pq.pop();
+      k--;
+    }
+
+    return w;
+  }
+};
diff --git a/README.md b/README.md
@@ -246,6 +246,7 @@ for solving problems.
 |  0496  |   Medium   | [Next Greater Element I](Problems/0496.cpp)                                                      |
 |  0498  |   Medium   | [Diagonal Traverse](Problems/0498.cpp)                                                           |
 |  0501  |    Easy    | [Find Mode in Binary Search Tree](Problems/0501.cpp)                                             |
+|  0502  |    Hard    | [IPO](Problems/0502.cpp)                                                                         |
 |  0503  |   Medium   | [Next Greater Element II](Problems/0503.cpp)                                                     |
 |  0509  |    Easy    | [Fibonacci Number](Problems/0509.cpp)                                                            |
 |  0516  |   Medium   | [Longest Palindromic Subsequence](Problems/0516.cpp)                                             |