oj.uz

Submission #13070

# Submission time Handle Problem Language Result Execution time Memory
13070 2015-01-30T16:24:43 Z dohyun0324 Luxury burrow (IZhO13_burrow) C++
44 / 100
 606 ms 9060 KB 
#include<stdio.h>
int n,m,k,a[1010][1010],b[1010][1010],top;
struct data
{
    int x,p;
}st[1010];
int pro(int x)
{
    int w,i,j,l,p=1,maxi=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i][j]>=x) b[i][j]=1;
            else b[i][j]=0;
        }
    }
    for(i=1;i<=m;i++){
        p=1;
        for(j=1;j<=n+1;j++){
            if(b[j][i]==0){
                w=0;
                for(l=j-1;l>=p;l--){
                    if(b[l][i]==0) break;
                    b[l][i]=++w;
                }
                p=j;
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            while(st[top].x>b[i][j] && top>0){
                if(maxi<(j-st[top].p)*st[top].x) maxi=(j-st[top].p)*st[top].x;
                top--;
            }
            top++;
            st[top].x=b[i][j]; st[top].p=j;
        }
        while(top>0){
            if(maxi<(m+1-st[top].p)*st[top].x) maxi=(m+1-st[top].p)*st[top].x;
            top--;
        }
    }
    return maxi;
}
void bsearch()
{
    int p,s=1,e=1000000000,mid;
    while(1){
        if(s==e) break;
        mid=(s+e)/2;
        p=pro(mid);
        if(p>=k) s=mid+1;
        else e=mid;
    }
    if(pro(s)>=k) s++;
    printf("%d %d",s-1,pro(s-1));
}
int main()
{
    int i,j;
    scanf("%d %d %d",&n,&m,&k);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    bsearch();
    return 0;
}

Subtask #1
44.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 0 ms 9060 KB Output is correct
4 Incorrect 0 ms 9060 KB Output isn't correct
5 Incorrect 0 ms 9060 KB Output isn't correct
6 Correct 0 ms 9060 KB Output is correct
7 Correct 1 ms 9060 KB Output is correct
8 Incorrect 5 ms 9060 KB Output isn't correct
9 Incorrect 9 ms 9060 KB Output isn't correct
10 Correct 22 ms 9060 KB Output is correct
11 Correct 40 ms 9060 KB Output is correct
12 Incorrect 24 ms 9060 KB Output isn't correct
13 Correct 34 ms 9060 KB Output is correct
14 Incorrect 63 ms 9060 KB Output isn't correct
15 Incorrect 76 ms 9060 KB Output isn't correct
16 Correct 87 ms 9060 KB Output is correct
17 Correct 81 ms 9060 KB Output is correct
18 Incorrect 213 ms 9060 KB Output isn't correct
19 Incorrect 226 ms 9060 KB Output isn't correct
20 Incorrect 446 ms 9060 KB Output isn't correct
21 Incorrect 399 ms 9060 KB Output isn't correct
22 Correct 606 ms 9060 KB Output is correct
23 Incorrect 553 ms 9060 KB Output isn't correct
24 Incorrect 361 ms 9060 KB Output isn't correct
25 Incorrect 421 ms 9060 KB Output isn't correct