1292.cpp (1341B)
1 class Solution { 2 mutable int n, m; 3 4 bool exists(const vector<vector<int>> &mat, const int threshold, const int side) const { 5 for (int i = 0; i < n - side; i++) { 6 for (int j = 0; j < m - side; j++) { 7 int crnt = mat[i + side][j + side]; 8 if (i > 0) crnt -= mat[i - 1][j + side]; 9 if (j > 0) crnt -= mat[i + side][j - 1]; 10 if (i > 0 && j > 0) crnt += mat[i - 1][j - 1]; 11 if (crnt <= threshold) return true; 12 } 13 } 14 return false; 15 } 16 17 public: 18 int maxSideLength(vector<vector<int>> &mat, const int threshold) const { 19 n = size(mat), m = size(mat[0]); 20 21 for (int i = 0, acc = 0; i < n; i++) 22 mat[i][0] = acc += mat[i][0]; 23 for (int j = 0, acc = 0; j < m; j++) 24 mat[0][j] = acc += mat[0][j]; 25 for (int i = 1; i < n; i++) { 26 for (int j = 1; j < m; j++) { 27 mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]; 28 } 29 } 30 31 int low = 1, high = min(n, m); 32 33 while (low <= high) { 34 const int mid = low + (high - low) / 2; 35 if (exists(mat, threshold, mid - 1)) 36 low = mid + 1; 37 else 38 high = mid - 1; 39 } 40 41 return high; 42 } 43 };