# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
699864 | vjudge1 | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,h,w;
int a[N][N],sum[N][N];
int get(int sx,int sy,int ex,int ey){return sum[ex][ey]-sum[sx-1][ey]-sum[ex][sy-1]+sum[sx-1][sy-1];}
int check(int mid)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=(a[i][j]>mid?-1:1)+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
for(int i=1;i+h-1<=n;i++)
for(int j=1;j+w-1<=m;j++)
if(get(i,j,i+h-1,j+w-1)>0)return 1;
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&h,&w);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
int l=0,r=n*m;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}