#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
int r, c;
int mat[MAXN][MAXN];
int sum(int r1, int c1, int r2, int c2) {
return mat[r2][c2] - mat[r1 - 1][c2] - mat[r2][c1 - 1] + mat[r1 - 1][c1 - 1];
}
bool check(int h, int w) {
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j)
mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
if (i + h - 1 > r || j + w - 1 > c) continue;
if (sum(i, j, i + h - 1, j + w - 1) > h * w / 2) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r = R; c = C;
int lo = 1, hi = R * C;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
mat[i + 1][j + 1] = Q[i][j] <= mid;
if (check(H, W)) hi = mid; else lo = mid + 1;
}
return lo;
}
