Submission #1108856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108856		brover29	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	1 ms	2384 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-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]*(n-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));
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d%d",&n,&m,&k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
burrow.cpp:54:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&a[i][j]);
      |                                   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100