leetcode

commit ed4fd2b6d328e91aa05e7c4eda3d386a846b68da
parent 47acae7b6715ade1a457a2c8c475577bde086911
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 24 Jun 2023 15:09:53 +0200

Daily Problem

Diffstat:
A
Problems/0956.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0956.cpp b/Problems/0956.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+  int tallestBillboard(const vector<int> &rods) {
+    int sum = accumulate(rods.begin(), rods.end(), 0);
+    vector<int> dp(sum + 1, -1);
+    dp[0] = 0;
+
+    for (int rod : rods) {
+      vector<int> dpc = dp;
+      for (int i = 0; i <= sum - rod; i++) {
+        if (dpc[i] < 0) continue;
+        dp[i + rod] = max(dp[i + rod], dpc[i]);
+        dp[abs(i - rod)] = max(dp[abs(i - rod)], dpc[i] + min(i, rod));
+      }
+    }
+    return dp[0];
+  }
+};
diff --git a/README.md b/README.md
@@ -385,6 +385,7 @@ for solving problems.
 |  0947  |   Medium   | [Most Stones Removed with Same Row or Column](Problems/0947.cpp)                                 |
 |  0950  |   Medium   | [Reveal Cards In Increasing Order](Problems/0950.cpp)                                            |
 |  0953  |    Easy    | [Verifying an Alien Dictionary](Problems/0953.cpp)                                               |
+|  0956  |   Medium   | [Tallest Billboard](Problems/0956.cpp)                                                           |
 |  0958  |   Medium   | [Check Completeness of a Binary Tree](Problems/0958.cpp)                                         |
 |  0959  |   Medium   | [Regions Cut By Slashes](Problems/0959.cpp)                                                      |
 |  0965  |    Easy    | [Univalued Binary Tree](Problems/0965.cpp)                                                       |