#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int a[3001][3001];
int getsum(int r1, int c1, int r2, int c2) {
return a[r2][c2] - a[r1 - 1][c2] - a[r2][c1 - 1] + a[r1 - 1][c1 - 1];
}
int rectangle(int n, int m, int h, int w, int matrix[3001][3001]) {
/// for the example the solution is 9
int low = 1, high = n * m, sol = -1;
while (low <= high) {
int want = (low + high) / 2;
bool ok = 0;
for (int i = 1; i <= n; i++) {
int current = 0;
for (int j = 1; j <= m; j++) {
if (matrix[i - 1][j - 1] > want) {
a[i][j] = -1;
} else {
if (matrix[i - 1][j - 1] < want) {
a[i][j] = +1;
} else {
a[i][j] = 0;
}
}
current += a[i][j];
a[i][j] = a[i - 1][j] + current;
}
}
for (int i = 1; i + h - 1 <= n; i++) {
for (int j = 1; j + w - 1 <= m; j++) {
if (getsum(i, j, i + h - 1, j + w - 1) >= 0) {
ok = 1;
}
}
}
if (ok) {
sol = want;
high = want - 1;
} else {
low = want + 1;
}
}
assert(sol != -1);
return sol;
}
