#include "quality.h"
#include "bits/stdc++.h"
using namespace std;
bool check(int k, int r, int c, int h, int w, int q[3001][3001]){
vector<vector<int>> cntp(r, vector<int>(c));
for (int i = 0; i < r; ++i){
for (int j = 0; j < c; ++j){
if (i != 0) cntp[i][j] += cntp[i-1][j];
if (j != 0) cntp[i][j] += cntp[i][j-1];
if (i != 0 && j != 0) cntp[i][j] -= cntp[i-1][j-1];
cntp[i][j] += q[i][j] <= k;
}
}
for (int i = h-1; i < r; ++i){
for (int j = w-1; j < c; ++j){
int cnt = cntp[i][j];
if (i != h-1) cnt -= cntp[i - h][j];
if (j != w-1) cnt -= cntp[i][j - w];
if (i != h-1 && j != w-1) cnt += cntp[i - h][j - w];
if (cnt > h * w / 2) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 1, r = R*C;
int bst = 0;
while (l <= r){
int mid = (l + r) / 2;
if (check(mid, R, C, H, W, Q)) bst = mid, r = mid - 1;
else l = mid + 1;
}
return bst;
}
