#include "quality.h"
#include <bits/stdc++.h>
int pref[3001][3001];
int arr[3003][3003];
int sum(int x1, int y1, int x2, int y2){
return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
}
bool check(int R, int C, int H, int W, int x){
for(int i = 1; i <= R;i++){
for(int j = 1; j <= C;j++){
if(arr[i][j] <= x)pref[i][j] = 1;
else pref[i][j] = 0;
pref[i][j]+=pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
for(int i = 1; i <= R;i++){
for(int j = 1;j<=C;j++){
int x2 = i + H - 1;
int y2 = j + W - 1;
if(x2 > R || y2 > C)break;
int rectSum = sum(i, j, x2, y2);
if(rectSum >= (H * W + 1) / 2)return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 1;
int r = 1e7;
for(int i = 1;i <= R;i++){
for(int j = 1; j <= C;j++){
arr[i][j] = Q[i - 1][j - 1];
}
}
while(r - l > 1){
int m = (l + r) / 2;
if(check(R, C, H, W, m)) r = m;
else l = m;
}
if(l == r){
return l;
}else{
if(check(R, C, H, W, l))return l;
else return r;
}
}
