leetcode

commit e41c31d07c5a3d23d84cf829b66a22d46d073f13
parent 4afb9e20130e7d4ba85d23741ce5959eb09ef0af
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  2 Jul 2023 15:36:42 +0200

Daily Problem

Diffstat:
A
Problems/1601.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/1601.cpp b/Problems/1601.cpp
@@ -0,0 +1,27 @@
+class Solution {
+  int degree[21] = {0};
+  int res = 0;
+
+  void rec(const vector<vector<int>> &req, int cur = 0, int cnt = 0,
+           int dirty = 0) {
+    if (cnt + (req.size() - cur) < res) return;
+    if (cur == req.size()) {
+      if (dirty) return;
+      res = max(res, cnt);
+      return;
+    }
+
+    rec(req, cur + 1, cnt, dirty);
+
+    if (degree[req[cur][0]]++ == 0) dirty++;
+    if (--degree[req[cur][1]] == 0) dirty--;
+    rec(req, cur + 1, cnt + 1, dirty);
+    degree[req[cur][0]]--, degree[req[cur][1]]++;
+  }
+
+public:
+  int maximumRequests(int n, const vector<vector<int>> &requests) {
+    rec(requests);
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -492,6 +492,7 @@ for solving problems.
 |  1575  |   Medium   | [Count All Possible Routes](Problems/1575.cpp)                                                   |
 |  1579  |    Hard    | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp)                  |
 |  1584  |   Medium   | [Min Cost to Connect All Points](Problems/1584.cpp)                                              |
+|  1601  |    Hard    | [Maximum Number of Achievable Transfer Requests](Problems/1601.cpp)                              |
 |  1603  |    Easy    | [Design Parking System](Problems/1603.cpp)                                                       |
 |  1609  |   Medium   | [Even Odd Tree](Problems/1609.cpp)                                                               |
 |  1615  |   Medium   | [Maximal Network Rank](Problems/1615.cpp)                                                        |