#include "quality.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int grid[3001][3001];
int R, C, H, W;
int** Q;
int b_search(int a, int b)
{
if(a == b) return a;
int m = (a+b)/2;
for(int i = 0; i <= R; i++) grid[i][0] = 0;
for(int j = 0; j <= C; j++) grid[0][j] = 0;
for(int i = 1; i <= R; i++)
{
for(int j = 1; j <= C; j++)
{
grid[i][j] = (Q[i-1][j-1] <= m);
grid[i][j] += grid[i-1][j];
grid[i][j] += grid[i][j-1];
grid[i][j] -= grid[i-1][j-1];
}
}
for(int i = H; i <= R; i++)
{
for(int j = W; j <= C; j++)
{
if(2*(grid[i][j] - grid[i-H][j] - grid[i][j-W] + grid[i-H][j-W]) >= H*W)
{
return b_search(a, m);
}
}
}
return b_search(m+1, b);
}
int rectangle(int r, int c, int h, int w, int q[3001][3001])
{
R = r;
C = c;
H = h;
W = w;
Q = new int*[3001];
for(int i = 0; i <= 3000; i++)
{
Q[i] = new int[3000];
for(int j = 0; j <= 3000; j++) Q[i][j] = q[i][j];
}
return b_search(0, R*C-1);
}
