#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int>> a(R + 1, vector<int>(C + 1));
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
a[i][j] = Q[i - 1][j - 1];
}
}
int l = 1, r = R * C;
vector<vector<int>> p(R + 1, vector<int>(C + 1, 0));
while (l != r){
int m = (l + r)/2;
bool good = false;
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
if (a[i][j] <= m) {
p[i][j]++;
// cout << i << " " << j << "\n";
}
}
}
// cout << m << "\n";
// for (int i = 1; i <= R; i++){
// for (int j = 1; j <= C; j++){
// cout << p[i][j] << " \n"[j == C];
// }
// }
for (int i = 1; i <= R; i++){
for (int j = 1; j <= C; j++){
int x = i + H - 1;
int y = j + W - 1;
if (x > R || y > C) continue;
int val = p[x][y] + p[i - 1][j - 1] - p[x][j - 1] - p[i - 1][y];
if (val > (H * W) / 2) good = true;
}
}
if (good) r = m;
else l = m + 1;
}
return l;
}
// int main(){
// int r, c, h, w; int Q[3001][3001];
// cin >> r >> c >> h >> w;
// for (int i = 1; i <= r; i++){
// for (int j = 1; j <= c; j++){
// cin >> Q[i - 1][j - 1];
// }
// }
// cout << rectangle(r, c, h, w, Q);
// return 0;
// }
