#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int lo = 1, hi = R * C;
auto ok = [&](int x) -> bool {
vector<vector<int>> v(R, vector<int>(C, 0));
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (Q[i][j] <= x) {
v[i][j] = 1;
}
}
}
for (int i = 0; i < R; ++i) {
for (int j = 1; j < C; ++j) {
v[i][j] += v[i][j - 1];
}
}
for (int i = 1; i < R; ++i) {
for (int j = 0; j < C; ++j) {
v[i][j] += v[i - 1][j];
}
}
for (int i = 0; i < R - H + 1; ++i) {
for (int j = 0; j < C - W + 1; ++j) {
int a = ((i > 0 && j > 0) ? v[i - 1][j - 1] : 0);
int b = (i > 0 ? v[i - 1][j + W - 1] : 0);
int c = (j > 0 ? v[i + H - 1][j - 1] : 0);
int d = v[i + H - 1][j + W - 1];
if (a + d - b - c > H * W / 2) return true;
}
}
return false;
};
while (hi > lo) {
int m = (lo + hi) / 2;
if (ok(m)) {
hi = m;
} else {
lo = m + 1;
}
}
return hi;
}
