#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3001;
int rectangle(int n,int m,int H,int W, int grid[MAXN][MAXN]){
int l=1, r = n * m;
int res = r;
vector<vector<int>> pre(n,vector<int>(m,0));
function<bool(int)> check = [&] (int mid) -> bool {
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
int cur = (grid[i][j] <= mid ? 1 : -1);
int upperHalf = (!i ? 0 : pre[i-1][j]);
int leftHalf = (!j ? 0 : pre[i][j-1]);
int overlap = ((i and j) ? pre[i-1][j-1] : 0);
pre[i][j] = upperHalf + leftHalf - overlap + cur;
}
}
for (int i = H-1; i < n; i++) {
for (int j = W-1; j < m; j++) {
int cur = pre[i][j]
- (i-H >= 0 ? pre[i-H][j] : 0)
- (j-W >= 0 ? pre[i][j-W] : 0)
+ (i-H >= 0 and j-W >= 0 ? pre[i-H][j-W] : 0);
if (cur > 0) return true;
}
}
return false;
};
while (l<=r){
int mid = (l+r)>>1;
if (check(mid)){
res = mid;
r=mid-1;
} else{
l = mid + 1;
}
}
return res;
}
