Submission #4767

#	Time	Username	Problem	Language	Result	Execution time	Memory
4767		gs13068	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	812 ms	8916 KiB

burrow

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

• Subtask 1: 100 / 100