#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;
int ans = 1;
while (l <= r) {
int mid = l + (r - l) / 2;
//cout << mid << " ";
bool possible = false, ok = false;
vector<vector<int>> nbSmaller (R, vector<int>(C - W + 1));
vector<vector<int>> nbBigger (R, vector<int>(C - W + 1));
for (int i = 0; i < R; i++) {
int cnt = 0, cnt2 = 0;
for (int j = 0; j < W; j++) {cnt += (Q[i][j] < mid); cnt2 += (Q[i][j] > mid);}
nbSmaller[i][0] = cnt;
nbBigger[i][0] = cnt2;
for (int j = 0; j < C - W; j++) {
cnt -= (Q[i][j] < mid);
cnt += (Q[i][j + W] < mid);
cnt2 -= (Q[i][j] > mid);
cnt2 += (Q[i][j + W] > mid);
nbSmaller[i][j + 1] = cnt;
nbBigger[i][j + 1] = cnt2;
}
}
/*cout << mid << '\n';
for (auto x : nbSmaller) {
for (auto y : x) cout << y << ' ';
cout << '\n';
}
cout << "\n\n";*/
for (int i = 0; i < C - W + 1; i++) {
int cnt = 0, cnt2 = 0;
for (int j = 0; j < H; j++) {cnt += nbSmaller[j][i]; cnt2 += nbBigger[j][i];}
if (cnt2 <= (W * H) / 2) {
possible = true;
if (cnt == cnt2 && cnt == W * H / 2) {
ok = true;
break;
}
}
for (int j = 0; j < R - H; j++) {
cnt -= nbSmaller[j][i];
cnt += nbSmaller[j + H][i];
cnt2 -= nbBigger[j][i];
cnt2 += nbBigger[j + H][i];
if (cnt2 <= (W * H) / 2) {
possible = true;
if (cnt == cnt2 && cnt == W * H / 2) {
ok = true;
break;
}
}
}
if (ok) break;
}
if (possible) {
//cout << "passed\n";
if (ok) ans = mid;
r = mid - 1;
}
else {
//cout << "failed\n";
l = mid + 1;
}
}
return ans;
}
