leetcode

commit 769fa3ed8f0cdcf3758b5acf2f1a5d40418e052e
parent dfedfb533e88455a89a0d208613a4738295d7b9d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 21 Apr 2023 19:50:08 +0200

Daily Problem

Diffstat:
A
Problems/0879.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/0879.cpp b/Problems/0879.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+  int profitableSchemes(int n, int minProfit, const vector<int> &group,
+                        const vector<int> &profit) {
+    int dp[101][101] = {{1}};
+    int res = 0, mod = 1e9 + 7;
+    for (int k = 0; k < group.size(); k++) {
+      int g = group[k], p = profit[k];
+      for (int i = minProfit; i >= 0; i--) {
+        for (int j = n - g; j >= 0; j--) {
+          int &cache = dp[min(i + p, minProfit)][j + g];
+          cache = (cache + dp[i][j]) % mod;
+        }
+      }
+    }
+    for (int x : dp[minProfit]) res = (res + x) % mod;
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -347,6 +347,7 @@ for solving problems.
 |  0872  |    Easy    | [Leaf-Similar Trees](Problems/0872.cpp)                                                          |
 |  0875  |   Medium   | [Koko Eating Bananas](Problems/0875.cpp)                                                         |
 |  0876  |    Easy    | [Middle of the Linked List](Problems/0876.cpp)                                                   |
+|  0879  |    Hard    | [Profitable Schemes](Problems/0879.cpp)                                                          |
 |  0881  |   Medium   | [Boats to Save People](Problems/0881.cpp)                                                        |
 |  0884  |    Easy    | [Uncommon Words from Two Sentences](Problems/0884.cpp)                                           |
 |  0886  |   Medium   | [Possible Bipartition](Problems/0886.cpp)                                                        |