oj.uz

Submission #4766

# Submission time Handle Problem Language Result Execution time Memory
4766 2014-01-01T08:49:50 Z ainta Luxury burrow (IZhO13_burrow) C++
12 / 100
 792 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
12.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8916 KB Output is 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 Correct 0 ms 8916 KB Output is correct
7 Incorrect 0 ms 8916 KB Output isn't correct
8 Incorrect 0 ms 8916 KB Output isn't correct
9 Incorrect 8 ms 8916 KB Output isn't correct
10 Correct 20 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 60 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 244 ms 8916 KB Output isn't correct
19 Incorrect 360 ms 8916 KB Output isn't correct
20 Incorrect 588 ms 8916 KB Output isn't correct
21 Incorrect 644 ms 8916 KB Output isn't correct
22 Incorrect 788 ms 8916 KB Output isn't correct
23 Incorrect 792 ms 8916 KB Output isn't correct
24 Incorrect 540 ms 8916 KB Output isn't correct
25 Incorrect 688 ms 8916 KB Output isn't correct