Submission #13077

#	Time	Username	Problem	Language	Result	Execution time	Memory
13077		dohyun0324	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	813 ms	9068 KiB

burrow

#include<stdio.h>
int n,m,k,a[1010][1010],b[1010][1010],arr1[1010],arr2[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){arr1[st[top].p]=j-1; top--;}
            top++;
            st[top].x=b[i][j]; st[top].p=j;
        }
        while(top>0){arr1[st[top].p]=m; top--;}
        for(j=m;j>=1;j--){
            while(st[top].x>b[i][j] && top>0){arr2[st[top].p]=j+1; top--;}
            top++;
            st[top].x=b[i][j]; st[top].p=j;
        }
        while(top>0){arr2[st[top].p]=1; top--;}
        for(j=1;j<=m;j++){
            if(maxi<(arr1[j]-arr2[j]+1)*b[i][j]) maxi=(arr1[j]-arr2[j]+1)*b[i][j];
        }
    }
    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: 100 / 100