#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 3005;
int csum[mx][mx];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
for(int i = R; i >= 1; i--){
for(int j = C; j >= 1; j--){
Q[i][j] = Q[i-1][j-1];
}
}
int lo = 1;
int hi = R*C;
while(lo < hi){
int mid = (lo+hi)/2;
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
if(Q[i][j] < mid){
csum[i][j] = -1;
}
else if(Q[i][j] > mid){
csum[i][j] = 1;
}
else{
csum[i][j] = 0;
}
}
}
// cout << "mid: " << mid << "\n";
// for(int i = 1; i <= R; i++){
// for(int j = 1; j <= C; j++){
// cout << csum[i][j] << " ";
// }
// cout << "\n";
// }
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
csum[i][j]+=csum[i-1][j]+csum[i][j-1]-csum[i-1][j-1];
}
}
// cout << "mid: " << mid << "\n";
// for(int i = 1; i <= R; i++){
// for(int j = 1; j <= C; j++){
// cout << csum[i][j] << " ";
// }
// cout << "\n";
// }
bool works = 0;
for(int i = H; i <= R; i++){
for(int j = W; j <= C; j++){
if(csum[i][j]-csum[i-H][j]-csum[i][j-W]+csum[i-H][j-W] <= 0){
//cout << mid << " " << i << " " << j << "\n";
works = 1;
break;
}
}
}
if(works){
hi = mid;
}
else{
lo = mid+1;
}
}
return lo;
}
