#include "quality.h"
int rectangle(int row, int col, int hig, int wid, int q[][3001])
{
int l = 1e9, r = -1e9;
for(int i = 0; i < row; ++i)
{
for(int j = 0; j < col; ++j)
{
if(l > q[i][j]) l = q[i][j];
if(r < q[i][j]) r = q[i][j];
}
}
int a[3001][3001], sum[3001][3001], ans;
while(l <= r)
{
int mid = (l + r) / 2;
for(int i = 1; i <= row; ++i)
{
for(int j = 1; j <= col; ++j)
{
if(q[i - 1][j - 1] <= mid) a[i][j] = 1;
else a[i][j] = -1;
}
}
for(int i = 1; i <= row; ++i)
{
for(int j = 1; j <= col; ++j)
{
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
bool check = false;
for(int x1 = 1; x1 <= row - hig + 1; ++x1)
{
for(int y1 = 1; y1 <= col - wid + 1; ++y1)
{
int x2 = x1 + hig - 1, y2 = y1 + wid - 1;
int res = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
if(res > 0) check = true;
if(check) break;
}
if(check) break;
}
if(check)
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
