leetcode

commit 8cebc5b3bd2dde4dd66a57c09c56a44c958de2d8
parent 7c0c5f9996cad24588d40f8184f9dfc906d55bd7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 24 May 2023 21:14:15 +0200

Daily Problem

Diffstat:
A
Problems/2542.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/2542.cpp b/Problems/2542.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  typedef pair<long long, long long> elem;
+
+public:
+  long long maxScore(vector<int> &nums1, vector<int> &nums2, int k) {
+    int n = nums1.size();
+    vector<elem> arr(n);
+    for (int i = 0; i < n; ++i) arr[i] = {nums2[i], nums1[i]};
+    sort(rbegin(arr), rend(arr));
+
+    long long sum = 0, res = 0;
+    priority_queue<int, vector<int>, greater<int>> pq;
+    for (auto &[a, b] : arr) {
+      pq.emplace(b);
+      sum += b;
+      if (pq.size() > k) {
+        sum -= pq.top();
+        pq.pop();
+      }
+      if (pq.size() == k) res = max(res, sum * a);
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -543,6 +543,7 @@ for solving problems.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 |  2497  |   Medium   | [Maximum Star Sum of a Graph](Problems/2497.cpp)                                                 |
+|  2542  |   Medium   | [Maximum Subsequence Score](Problems/2542.cpp)                                                   |
 |  2620  |    Easy    | [Counter](Problems/2620.js)                                                                      |
 |  2621  |    Easy    | [Sleep](Problems/2621.js)                                                                        |
 |  2622  |   Medium   | [Cache With Time Limit](Problems/2622.js)                                                        |