#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int cnt[3005][3005], q[3005][3005];
bool check(int num, int r, int c, int h, int w)
{
//cout<<num<<endl;
memset(cnt, 0, sizeof(cnt));
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
{
//cout<<cnt[i-1][j]<<' '<<cnt[i][j-1]<<' '<<cnt[i-1][j-1]<<' '<<q[i][j]<<' '<<(q[i][j]<num)<<endl;
cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+(q[i][j]<=num)/*, cout<<i<<' '<<j<<' '<<cnt[i][j]<<endl*/;
}
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
if(i+h-1>r) continue;
if(j+w-1>c) continue;
int sum=cnt[i+h-1][j+w-1]-cnt[i-1][j+w-1]-cnt[i+h-1][j-1]+cnt[i-1][j-1];
//cout<<"sum "<<i<<' '<<j<<' '<<sum<<endl;
if(sum>h*w/2) return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int l=1, r=R*C, mid;
for(int i=0; i<R; i++)
{
for(int j=0; j<C; j++)
{
q[i+1][j+1]=Q[i][j];
}
}
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid, R, C, H, W)) r=mid-1;
else l=mid+1;
}
return l;
}
