#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int>> vvi(R + 1, vector<int>(C + 1));
auto helper = vvi;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
vvi[i + 1][j + 1] = Q[i][j];
int l = 1, r = R * C;
while (l < r) {
int mid = (l + r) / 2;
helper.assign(R + 1, vector<int>(C + 1));
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (vvi[i][j] <= mid)
helper[i][j] = 1;
helper[i][j] +=
helper[i - 1][j] + helper[i][j - 1] - helper[i - 1][j - 1];
}
}
// cout << mid << "\n";
// for (auto a : helper) {
// for (auto b : a)
// cout << b << " ";
// cout << "\n";
// }
int maxi = 0;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
int res = helper[min(R, i + H - 1)][min(C, j + W - 1)] -
helper[min(R, i + H - 1)][j - 1] -
helper[i - 1][min(C, j + W - 1)] + helper[i - 1][j - 1];
// cout << i << " " << j << " " << res << "\n";
maxi = max(maxi, res);
}
}
// cout << maxi << "\n";
if (maxi >= (H * W) / 2 + 1) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
