leetcode

commit eed45a8b7b9e5662b7a144ac383df751b3139fc0
parent 0e5b14df572cb5927b6c33f0eb1c046e72684dd6
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 29 Apr 2024 16:49:13 +0200

1 Random Problem

Diffstat:
M
Problems/1895.cpp
 | 
44
+++++++++++++++++++++++++++++++++++++-------
M
README.md
 | 
1
+

2 files changed, 38 insertions(+), 7 deletions(-)
diff --git a/Problems/1895.cpp b/Problems/1895.cpp
@@ -1,12 +1,42 @@
 class Solution {
   public:
-    int minProcessingTime(vector<int> &processorTime, vector<int> &tasks) {
-        sort(begin(processorTime), end(processorTime));
-        sort(begin(tasks), end(tasks));
-        int res = 0;
-        for (int i = 0; i < tasks.size(); i++) {
-            res = max(res, processorTime[i >> 2] + tasks[tasks.size() - i - 1]);
+    int largestMagicSquare(const vector<vector<int>> &grid) const {
+        static int row[51][51] = {}, col[51][51] = {};
+        const int n = size(grid), m = size(grid[0]);
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++)
+                row[i + 1][j + 1] = row[i + 1][j] + grid[i][j];
         }
-        return res;
+
+        for (int j = 0; j < m; j++) {
+            for (int i = 0; i < n; i++)
+                col[i + 1][j + 1] = col[i][j + 1] + grid[i][j];
+        }
+
+        for (int k = min(n, m); k > 1; k--) {
+            for (int i = k; i <= n; i++) {
+                for (int j = k; j <= m; j++) {
+                    const int r = row[i][j] - row[i][j - k];
+                    const int c = col[i][j] - col[i - k][j];
+                    int d1 = 0, d2 = 0;
+
+                    if (r != c) goto nothing;
+                    for (int l = 0; l < k; l++) {
+                        if (r != row[i - l][j] - row[i - l][j - k]) goto nothing;
+                        if (c != col[i][j - l] - col[i - k][j - l]) goto nothing;
+                        d1 += grid[i - k + l][j - k + l];
+                        d2 += grid[i - l - 1][j - k + l];
+                    }
+
+                    if (d1 != d2 || d1 != r) goto nothing;
+
+                    return k;
+                nothing:;
+                }
+            }
+        }
+
+        return 1;
     }
 };
diff --git a/README.md b/README.md
@@ -967,6 +967,7 @@ for solving problems.
 |  1884  |   Medium   | [Egg Drop With 2 Eggs and N Floors](Problems/1884.cpp)                                             |
 |  1887  |   Medium   | [Reduction Operations to Make the Array Elements Equal](Problems/1887.cpp)                         |
 |  1890  |    Easy    | [The Latest Login in 2020](Problems/1890.cpp)                                                      |
+|  1895  |   Medium   | [Largest Magic Square](Problems/1895.cpp)                                                          |
 |  1897  |    Easy    | [Redistribute Characters to Make All Strings Equal](Problems/1897.cpp)                             |
 |  1899  |   Medium   | [Merge Triplets to Form Target Triplet](Problems/1899.cpp)                                         |
 |  1903  |    Easy    | [Largest Odd Number in String](Problems/1903.cpp)                                                  |