#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXR 3005
#define MAXC 3005
#define INF (int)1e9
int height,width,rows,cols;
int q[3005][3005];
int cnt[3005];
bool check(int x){
for(int c=1;c<=cols;c++){
cnt[c]=0;
for(int r=1;r<height;r++){
cnt[c]+=(q[r][c]<=x);
}
}
for(int r=1;r+height-1<=rows;r++){
//update
for(int c=1;c<=cols;c++){
cnt[c]+=((q[r+height-1][c]<=x)-(q[r-1][c]<=x));
}
int ctr=0;
for(int c=1;c<width;c++){
ctr+=cnt[c];
}
//slide
for(int c=1;c+width-1<=cols;c++){
//update
ctr+=(cnt[c+width-1]-cnt[c-1]);
if(ctr>=((height*width+1)/2)){
return true;
}
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
rows=R;
cols=C;
height=H;
width=W;
for(int r=0;r<rows;r++){
for(int c=0;c<cols;c++){
q[r+1][c+1]=Q[r][c];
}
}
for(int r=1;r<=rows;r++){
q[r][0]=INF;
}
for(int c=1;c<=cols;c++){
q[0][c]=INF;
}
//binary search
int k=R*C;
for(int b=R*C-1;b>0;b/=2){
while(k-b>0&&check(k-b)) k-=b;
}
return k;
}
