leetcode

commit 8adc9eed81d0c940bfce3e1f9fc8577c411830b2
parent e4f8c09e23ae3fba89856db49b5ef3dc9d7dc8e7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 17 Aug 2024 23:50:37 +0200

Daily Problem

Diffstat:
A
Problems/1937.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/1937.cpp b/Problems/1937.cpp
@@ -0,0 +1,28 @@
+class Solution {
+  public:
+    long long maxPoints(vector<vector<int>> &points) const {
+        const int n = size(points), m = size(points[0]);
+        static long long crnt[100001], left[100001], right[100001];
+
+        for (int j = 0; j < m; j++)
+            crnt[j] = points[0][j];
+        for (int i = 1; i < n; i++) {
+
+            left[0] = crnt[0];
+            for (int j = 1; j < m; j++) {
+                left[j] = max(left[j - 1], crnt[j] + j);
+            }
+
+            right[m - 1] = crnt[m - 1] - (m - 1);
+            for (int j = m - 2; j >= 0; j--) {
+                right[j] = max(right[j + 1], crnt[j] - j);
+            }
+
+            for (int j = 0; j < m; j++) {
+                crnt[j] = points[i][j] + max(left[j] - j, right[j] + j);
+            }
+        }
+
+        return *max_element(crnt, crnt + m);
+    }
+};
diff --git a/README.md b/README.md
@@ -1036,6 +1036,7 @@ for solving problems.
 |  1929  |    Easy    | [Concatenation of Array](Problems/1929.cpp)                                                        |
 |  1930  |   Medium   | [Unique Length-3 Palindromic Subsequences](Problems/1930.cpp)                                      |
 |  1934  |   Medium   | [Confirmation Rate](Problems/1934.cpp)                                                             |
+|  1937  |   Medium   | [Maximum Number of Points with Cost](Problems/1937.cpp)                                            |
 |  1943  |   Medium   | [Describe the Painting](Problems/1943.cpp)                                                         |
 |  1947  |   Medium   | [Maximum Compatibility Score Sum](Problems/1947.cpp)                                               |
 |  1954  |   Medium   | [Minimum Garden Perimeter to Collect Enough Apples](Problems/1954.cpp)                             |