Submission #4761

#	Time	Username	Problem	Language	Result	Execution time	Memory
4761		gs13068	호화 벙커 (IZhO13_burrow)	C++98	0 / 100	848 ms	8916 KiB

burrow

#include<cstdio>

int a[1000][1000];
int d[1000][1000];
int s[2000],p[2000],sn;
int n,m,k;

bool 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<d[i][j]*(i-p[sn-1]))
          max=d[i][j]*(i-p[sn-1]);
        sn--;
      }
      s[sn]=d[i][j];
      p[sn]=i;
      sn++;
    }
    while(sn)
    {
      if(max<d[i][j]*(i-p[sn-1]))
        max=d[i][j]*(i-p[sn-1]);
      sn--;
    }
  }
  return max>=k;
}

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))l=mid;
    else r=mid-1;
  }
  printf("%d",l);
}

• Subtask 1: 0 / 100