Submission #13070

#	Time	Username	Problem	Language	Result	Execution time	Memory
13070		dohyun0324	Luxury burrow (IZhO13_burrow)	C++98	44 / 100	606 ms	9060 KiB

burrow

#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 / 100