#include "quality.h"
#include <functional>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int pfx[3001][3001];
function<bool(int)> check = [&](int x)
{
for (int i = 1; i <= R; ++i)
{
for (int j = 1; j <= C; ++j)
{
if (Q[i-1][j-1] > x) pfx[i][j] = -1;
else pfx[i][j] = 1;
pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];
}
}
int mx = -1e9;
for (int i = 1; i <= R-H+1; ++i)
{
for (int j = 1; j <= C-W+1; ++j)
{
//sum from (i, j) to (i+H-1, j+W-1)
mx = max(mx, pfx[i+H-1][j+W-1] - pfx[i+H-1][j-1] - pfx[i-1][j+W-1] + pfx[i-1][j-1]);
}
}
return mx >= 0;
};
int l = 1, r = R*C;
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
