#include "quality.h"
#include <iostream>
using namespace std;
int b[3001][3001], c[3001][3001], maxx, minn;
int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
int l = 1, r = n*m;
while (l <= r) {
int mid = (l+r)/2;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[i][j] = c[i][j] = 0;
for (int j = 0; j < m; j++) {
for (int i = 0; i < h; i++) {
if (a[i][j] > mid) b[0][j]++;
else c[0][j]++;
}
for (int i = 0; i+h < n; i++) {
b[i+1][j] = b[i][j];
c[i+1][j] = c[i][j];
if (a[i][j] > mid) b[i+1][j]--;
else c[i+1][j]--;
if (a[i+h][j] > mid) b[i+1][j]++;
else c[i+1][j]++;
}
}
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << b[i][j] << " ";
} cout << endl;
}*/
for (int i = 0; i+h-1 < n; i++) {
maxx = minn = 0;
for (int j = 0; j < w; j++) maxx += b[i][j], minn += c[i][j];
if (minn > maxx) {
r = mid-1;
goto skip;
}
for (int j = w; j < m; j++) {
maxx -= b[i][j-w];
minn -= c[i][j-w];
maxx += b[i][j];
minn += c[i][j];
if (minn > maxx) {
r = mid-1;
goto skip;
}
}
}
l = mid+1;
skip:;
}
return l;
}
