Quality of Life

QOL.cpp

#include<iostream>
using namespace std;
int Q[3001][3001],I[3001][3001],R,C,N,H,W,T;

void BI1(int k,int i){
    I[i][0]=(Q[i][0]>k)? 0:1;
    for(int j=1;j<C;j++){
	    I[i][j]=((Q[i][j]>k)? 0:1)+I[i][j-1];
	}
}

void BI2(int k, int j){
    for(int i=1;i<R;i++){
	    I[i][j]+=I[i-1][j];
	}
}

int cuan(int i,int j){
    int t=0;
    t+=I[i+H-1][j+W-1];
    if(i>0) t-=I[i-1][j+W-1];
    if(j>0) t-=I[i+H-1][j-1];
    if(i>0&&j>0) t+=I[i-1][j-1];
    return t;
}

int tst(int m){
    for(int i=0;i<R-H+1; i++) for(int j=0;j<C-W+1;j++){
	    if(cuan(i,j)>T) return 1;
	}
	return 0;
}

int BB(int a,int b){
	int m;
	m=(a+b)/2;
    if(a!=b){
	    for(int i=0;i<R;i++){
		    BI1(m,i);
		}
	    for(int j=0;j<C;j++){
		    BI2(m,j);
		}
	    if(tst(m)==0) return BB(m+1,b);
	    else return BB(a,m);
    }
    else{
	    return a;
	}
}

int main (){
	int i,j;
	cin >> R >> C >> H >> W;
	for(i=0;i<R;i++) for(j=0;j<C;j++)  cin >> Q[i][j];
	T=(H*W-1)/2;
    N=R*C;
	cout << BB(1,N);
	return 0;
}