#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 0, r = 3001 * 3001;
while (l + 1 < r) {
int m = (l + r) / 2;
vector<vector<int>> a(R, vector<int>(C));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
a[i][j] = Q[i][j] <= m;
}
}
vector<vector<int>> p(R + 1, vector<int>(C + 1));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
p[i + 1][j + 1] = a[i][j];
}
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
}
auto get = [&](int i, int j) {
return p[i + H][j + W] - p[i + H][j] - p[i][j + W] + p[i][j];
};
bool ok = 0;
for (int i = 0; i + H <= R; i++) {
for (int j = 0; j + W <= C; j++) {
if (get(i, j) >= (H * W + 1) / 2) {
ok = 1;
break;
}
}
}
if (ok) {
r = m;
} else {
l = m;
}
}
return r;
}
