oj.uz

Submission #4761

# Submission time Handle Problem Language Result Execution time Memory
4761 2014-01-01T08:33:15 Z gs13068 Luxury burrow (IZhO13_burrow) C++
0 / 100
 848 ms 8916 KB 
#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.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 4 ms 8916 KB Output isn't correct
9 Incorrect 4 ms 8916 KB Output isn't correct
10 Incorrect 28 ms 8916 KB Output isn't correct
11 Incorrect 32 ms 8916 KB Output isn't correct
12 Incorrect 16 ms 8916 KB Output isn't correct
13 Incorrect 32 ms 8916 KB Output isn't correct
14 Incorrect 52 ms 8916 KB Output isn't correct
15 Incorrect 56 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 240 ms 8916 KB Output isn't correct
19 Incorrect 352 ms 8916 KB Output isn't correct
20 Incorrect 560 ms 8916 KB Output isn't correct
21 Incorrect 656 ms 8916 KB Output isn't correct
22 Incorrect 744 ms 8916 KB Output isn't correct
23 Incorrect 848 ms 8916 KB Output isn't correct
24 Incorrect 552 ms 8916 KB Output isn't correct
25 Incorrect 740 ms 8916 KB Output isn't correct