#include <bits/stdc++.h>
using namespace std;
vector<vector<int> >precompute(int n, int m, vector<vector<int> >&massiv)
{
vector<vector<int> >preff(n + 1, vector<int>(m + 1));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
preff[i + 1][j + 1] = preff[i][j + 1] + preff[i + 1][j] + massiv[i][j] - preff[i][j];
}
}
return preff;
}
int query(int lx, int ly, int rx, int ry, vector<vector<int> >&preff)
{
return preff[rx][ry] - preff[rx][ly - 1] - preff[lx - 1][ry] + preff[lx - 1][ly - 1];
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int> >prefsum(R + 1, vector<int>(C + 1));
int l = 1;
int r = R * C;
vector<vector<int> >tmp;
for(int i = 0; i < R; i++)
{
vector<int>row;
for(int j = 0; j < C; j++)
{
row.push_back(Q[i][j]);
}
tmp.push_back(row);
}
int ans = R * C;
while(l <= r)
{
int mid = l + (r - l) / 2;
int lim = H * W / 2 + 1;
vector<vector<int> >tmp1 = tmp;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
if(tmp1[i][j] > mid)tmp1[i][j] = 0;
else tmp1[i][j] = 1;
}
}
vector<vector<int> >preff = precompute(R, C, tmp1);
int sig = 0;
int maxx = 0;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
if(i + H - 1 < R && j + W - 1 < C)
{
int sum = query(i + 1, j + 1, i + H, j + W, preff);
maxx = max(maxx, sum);
if(sum == lim)
{
sig = 1;
break;
}
}
}
if(sig)break;
}
if(sig){ans = min(ans, mid); r = mid - 1;}
else if(maxx > lim) r = mid - 1;
else l = mid + 1;
}
return ans;
}
