leetcode

commit b49f436b8aa7668c088dd74702116afd0cf37836
parent dc65284cdcd3a2cb4f4d9a79c003cd55c517018b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  5 Apr 2024 20:09:19 +0200

1 Random Problem

Diffstat:
A
Problems/0638.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/0638.cpp b/Problems/0638.cpp
@@ -0,0 +1,43 @@
+class Solution {
+    static bool finished(const vector<int> needs) {
+        for (const int n : needs)
+            if (n) return false;
+        return true;
+    }
+
+  public:
+    int shoppingOffers(const vector<int> &price, const vector<vector<int>> &special, const vector<int> &needs,
+                       int offer = 0, int cost = 0) const {
+        if (finished(needs)) return cost;
+
+        const int n = size(price);
+
+        int res = cost;
+        for (int i = 0; i < n; i++) {
+            res += needs[i] * price[i];
+        }
+
+        for (int i = offer; i < size(special); i++) {
+            int times = INT_MAX;
+            for (int j = 0; j < n && times; j++) {
+                if (!special[i][j]) continue;
+                times = min(times, needs[j] / special[i][j]);
+            }
+
+            if (!times) continue;
+
+            vector<int> next = needs;
+            int added = 0;
+
+            for (int k = 1; k <= times; k++) {
+                added += special[i].back();
+                if (cost + added >= res) break;
+                for (int j = 0; j < n; j++)
+                    next[j] -= special[i][j];
+                res = min(res, shoppingOffers(price, special, next, i + 1, cost + added));
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -418,6 +418,7 @@ for solving problems.
 |  0629  |    Hard    | [K Inverse Pairs Array](Problems/0629.cpp)                                                         |
 |  0636  |   Medium   | [Exclusive Time of Functions](Problems/0636.cpp)                                                   |
 |  0637  |    Easy    | [Average of Levels in Binary Tree](Problems/0637.cpp)                                              |
+|  0638  |   Medium   | [Shopping Offers](Problems/0638.cpp)                                                               |
 |  0641  |   Medium   | [Design Circular Deque](Problems/0641.cpp)                                                         |
 |  0643  |    Easy    | [Maximum Average Subarray I](Problems/0643.cpp)                                                    |
 |  0645  |    Easy    | [Set Mismatch](Problems/0645.cpp)                                                                  |