# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
699868 | vjudge1 | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}