#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int smaller[R+1][C+1] , bigger[R+1][C+1] , arr[R+1][C+1];
//make grid 1-indexed
memset(smaller , 0 , sizeof(smaller)) ;
memset(bigger , 0 , sizeof(bigger)) ;
for(int i = 1 ; i <= R ; ++i)
{
for(int j = 1 ; j <= C ; ++j)
arr[i][j] = Q[i-1][j-1] ;
}
int l = 1 , r = R*C , ans = R*C ;
while(l <= r)
{
int mid = (l + r) / 2 ;
for(int i = 1 ; i <= R ; ++i)
{
int s = 0 , b = 0 ;
for(int j = 1 ; j <= C ; ++j)
{
smaller[i][j] = s + smaller[i-1][j];
if(arr[i][j] < mid)
smaller[i][j]++ , ++s;
bigger[i][j] = b + bigger[i-1][j] ;
if(arr[i][j] > mid)
bigger[i][j]++ , ++b;
}
}
bool t = false ;
for(int i = 1 ; i <= R-H+1 ; ++i)
{
for(int j = 1 ; j <= C-W+1 ; ++j)
{
int s = smaller[i+H-1][j+W-1] - smaller[i+H-1][j-1] - smaller[i-1][j+W-1] + smaller[i-1][j-1] ;
int b = bigger[i+H-1][j+W-1] - bigger[i+H-1][j-1] - bigger[i-1][j+W-1] + bigger[i-1][j-1] ;
if(s >= b)
t = true ;
int n = R*C ;
if(s == b && s <= n/2 && b <= n/2)
ans = min(ans , mid) ;
}
}
if(t == true)
r = mid-1 ;
else
l = mid+1 ;
}
return ans ;
}
