oj.uz

Submission #4762

# Submission time Handle Problem Language Result Execution time Memory
4762 2014-01-01T08:34:05 Z gs13068 Luxury burrow (IZhO13_burrow) C++
0 / 100
 900 ms 8916 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<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;
}

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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 8916 KB Output isn't correct
2 Incorrect 0 ms 8916 KB Output isn't correct
3 Incorrect 0 ms 8916 KB Output isn't correct
4 Incorrect 0 ms 8916 KB Output isn't correct
5 Incorrect 0 ms 8916 KB Output isn't correct
6 Incorrect 0 ms 8916 KB Output isn't correct
7 Incorrect 0 ms 8916 KB Output isn't correct
8 Incorrect 0 ms 8916 KB Output isn't correct
9 Incorrect 4 ms 8916 KB Output isn't correct
10 Incorrect 24 ms 8916 KB Output isn't correct
11 Incorrect 36 ms 8916 KB Output isn't correct
12 Incorrect 20 ms 8916 KB Output isn't correct
13 Incorrect 36 ms 8916 KB Output isn't correct
14 Incorrect 60 ms 8916 KB Output isn't correct
15 Incorrect 68 ms 8916 KB Output isn't correct
16 Incorrect 64 ms 8916 KB Output isn't correct
17 Incorrect 72 ms 8916 KB Output isn't correct
18 Incorrect 288 ms 8916 KB Output isn't correct
19 Incorrect 376 ms 8916 KB Output isn't correct
20 Incorrect 660 ms 8916 KB Output isn't correct
21 Incorrect 700 ms 8916 KB Output isn't correct
22 Incorrect 792 ms 8916 KB Output isn't correct
23 Incorrect 900 ms 8916 KB Output isn't correct
24 Incorrect 616 ms 8916 KB Output isn't correct
25 Incorrect 764 ms 8916 KB Output isn't correct