제출 #13077

#제출 시각아이디문제언어결과실행 시간메모리
13077dohyun0324호화 벙커 (IZhO13_burrow)C++98
100 / 100
813 ms9068 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...