#include "quality.h"
#include <iostream>
#include <vector>
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int lo = 1, hi = R * C;
while (lo < hi) {
int mid = (lo + hi) / 2;
std::vector<std::vector<int>> prefixsum(R + 1, std::vector<int>(C + 1));
bool ok = false;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
prefixsum[i + 1][j + 1] = prefixsum[i][j + 1] + prefixsum[i + 1][j] + (Q[i][j] > mid) - prefixsum[i][j];
// std::cout << "prefixsum[" << i + 1 << "][" << j + 1 << "]=" << prefixsum[i + 1][j + 1] << '\n';
if (i + 1 >= H && j + 1 >= W) {
int val = prefixsum[i + 1][j + 1] + prefixsum[i + 1 - H][j + 1 - W] - prefixsum[i + 1 - H][j + 1] - prefixsum[i + 1][j + 1 - W];
// std::cout << "for mid=" << mid << " for i=" << i << " and j=" << j << " val is " << val << '\n';
ok |= (val <= H * W / 2);
}
}
}
if (ok) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
