#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int r, c, h, w;
vector<vector<int> > v(maxn, vector<int>(maxn));
bool check(int d) // cisla mensie ako d budu -1 a cisla vacsie ako d budu 1
{
vector<vector<int>> pf(r+1, vector<int>(c+1, 0));
for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
pf[i+1][j+1] = (v[i][j] > d ? -1 : 1) + pf[i+1][j] + pf[i][j+1] - pf[i][j];
for (int i = h; i <= r; i++)
{
for (int j = w; j <= c; j++)
{
int sum = pf[i][j] - pf[i-h][j] - pf[i][j-w] + pf[i-h][j-w];
if (sum > 0) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r = R, c = C, h = H, w = W;
for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
v[i][j] = Q[i][j];
int lo = 1, hi = (r * c);
while (lo < hi)
{
int mi = (lo + hi) / 2;
if (check(mi)) hi = mi;
else lo = mi+1;
}
return lo;
}
