#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#include "grader.h"
///#include "quality.h"
using namespace std;
const int lim = 36e4;
int st[lim + 2];
void update(int nodo, int l, int r, int pos, int x){
if(l > pos || r < pos){
return;
}
if(l == r){
st[nodo] += x;
return;
}
int mitad = (l + r) / 2;
update(nodo * 2, l, mitad, pos, x);
update(nodo * 2 + 1, mitad + 1, r, pos, x);
st[nodo] = st[nodo * 2] + st[nodo * 2 + 1];
}
int query(int nodo, int l, int r, int buscado, int acu){
if(l == r){
return l;
}
int mitad = (l + r) / 2;
return (st[nodo * 2] + acu < buscado) ? query(nodo * 2 + 1, mitad + 1, r, buscado, acu + st[nodo * 2]) : query(nodo * 2, l, mitad, buscado, acu);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int res = INT_MAX;
int buscado = (H * W) / 2;
buscado ++;
forn(i, 0, R - H){
forn(j, i, i + H - 1){
forn(k, 0, W - 1){
update(1, 1, R * C, Q[j][k], 1);
}
}
res = min(res, query(1, 1, R * C, buscado, 0));
forn(j, 1, C - W){
forn(k, i, i + H - 1){
update(1, 1, R * C, Q[k][j - 1], -1);
}
forn(k, i, i + H - 1){
update(1, 1, R * C, Q[k][j + W - 1], 1);
}
res = min(res, query(1, 1, R * C, buscado, 0));
}
forn(j, i, i + H - 1){
forn(k, C - W, C - 1){
update(1, 1, R * C, Q[j][k], -1);
}
}
}
return res;
}
