oj.uz

Submission #4764

# Submission time Handle Problem Language Result Execution time Memory
4764 2014-01-01T08:36:18 Z gs13068 Luxury burrow (IZhO13_burrow) C++
32 / 100
 872 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<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));
}

Subtask #1
32.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8916 KB Output is correct
2 Correct 0 ms 8916 KB Output is 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 Correct 0 ms 8916 KB Output is correct
7 Incorrect 0 ms 8916 KB Output isn't correct
8 Correct 4 ms 8916 KB Output is correct
9 Incorrect 4 ms 8916 KB Output isn't correct
10 Correct 16 ms 8916 KB Output is correct
11 Incorrect 28 ms 8916 KB Output isn't correct
12 Incorrect 20 ms 8916 KB Output isn't correct
13 Incorrect 24 ms 8916 KB Output isn't correct
14 Incorrect 60 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 Correct 68 ms 8916 KB Output is correct
18 Incorrect 244 ms 8916 KB Output isn't correct
19 Incorrect 392 ms 8916 KB Output isn't correct
20 Incorrect 588 ms 8916 KB Output isn't correct
21 Incorrect 668 ms 8916 KB Output isn't correct
22 Correct 872 ms 8916 KB Output is correct
23 Incorrect 864 ms 8916 KB Output isn't correct
24 Incorrect 596 ms 8916 KB Output isn't correct
25 Correct 756 ms 8916 KB Output is correct