| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 4763 | 2014-01-01T08:36:01 Z | gs13068 | 호화 벙커 (IZhO13_burrow) | C++ | 0 ms | 0 KB |
#include<cstdio>
int a[1000][1000];
int d[1000][1000];
int s[2000],p[2000],sn;
int n,m,k;
int possible(int x)
{
int i,j,max=0;
for(i=0;i<n;i++)
{
if(a[i][0]>=x)d[i][0]=1;
else d[i][0]=0;
for(j=1;j<m;j++)
{
if(a[i][j]>=x)d[i][j]=d[i][j-1]+1;
else d[i][j]=0;
}
}
for(j=0;j<m;j++)
{
sn=0;
s[sn]=0;
p[sn]=-1;
sn++;
for(i=0;i<n;i++)
{
while(sn&&s[sn-1]>d[i][j])
{
if(max<s[sn-1]*(i-p[sn-1]))
max=s[sn-1]*(i-p[sn-1]);
sn--;
}
s[sn]=d[i][j];
p[sn]=i;
sn++;
}
while(sn)
{
if(max<*(s[sn-1]-p[sn-1]))
max=s[sn-1]*(n-p[sn-1]);
sn--;
}
}
return max;
}
int main()
{
int l,r,mid;
int i,j;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&a[i][j]);
l=1;
r=1000000000;
while(l<r)
{
mid=(l+r+1)/2;
if(possible(mid)>=k)l=mid;
else r=mid-1;
}
printf("%d %d",l,possible(l));
}