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