#include "quality.h"
const int MAXN = 3024;
int q[MAXN][MAXN];
int pref[MAXN][MAXN];
int n, m, h, w;
bool check(int x)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
if(q[i][j]<=x)
{
pref[i][j]++;
}
}
}
for(int i=h;i<=n;i++)
{
for(int j=w;j<=m;j++)
{
int cnt=pref[i][j]-pref[i-h-1][j]-pref[i][j-w-1]+pref[i-h-1][j-w-1];
if(cnt>=(h*w)/2+1)return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
n=R;
m=C;
h=H;
w=W;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
q[i][j]=Q[i-1][j-1];
}
}
int l=1;
int r=n*m;
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
