#include <vector>
#include <iostream>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
// prefix sum
vector<vector<int>> pre(R + 1, vector<int>(C + 1, 0));
int l = 1, r = R * C, ans = 0;
while (l <= r)
{
int m = (l + r) / 2; // target
for (int i = 1; i <= R; ++i)
{
fill(pre[i].begin(), pre[i].end(), 0);
for (int j = 1; j <= C; ++j)
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + (Q[i - 1][j - 1] <= m);
}
bool found = 0;
for (int i = H; i <= R; ++i)
{
for (int j = W; j <= C; ++j)
{
int s = pre[i][j] - pre[i - H][j] - pre[i][j - W] + pre[i - H][j - W];
if (s >= (H * W + 1) / 2)
found = 1;
}
}
if (found)
ans = m, r = m - 1;
else
l = m + 1;
}
return ans;
}
