#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
igrid VC;
bool check (int R, int C, int H, int W, igrid &V, int M) {
int count = (H * W + 1) >> 1;
for (int i = 0; i <= R; i ++)
VC[i][0] = 0;
for (int i = 0; i <= C; i ++)
VC[0][i] = 0;
for (int i = 1; i <= R; i ++) {
for (int j = 1; j <= C; j ++) {
VC[i][j] = VC[i - 1][j]
+ VC[i][j - 1]
- VC[i - 1][j - 1]
+ (V[i - 1][j - 1] <= M ? 1 : 0);
}
}
for (int i = 0; i + H <= R; i ++) {
for (int j = 0; j + W <= C; j ++) {
int lc = VC[i][j] + VC[i + H][j + W]
- (VC[i + H][j] + VC[i][j + W]);
if (lc >= count) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
VC.resize(R + 1, idata(C + 1));
igrid V(R, idata(C));
for (int i = 0; i < R; i ++)
for (int j = 0; j < C; j ++)
V[i][j] = Q[i][j];
int a = 0;
int b = R * C;
while (b - a > 1) {
int c = (a + b) >> 1;
if (check(R, C, H, W, V, c)) b = c;
else a = c;
}
return b;
}
