Cod sursa(job #1815318)

Utilizator andra1782Andra Alazaroaie andra1782 Data 25 noiembrie 2016 01:53:14
Problema BMatrix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <stdio.h>
#define MAX 201
#define maxim(a,b) a<b ? b:a
char t[MAX][MAX];
int m,n,st[MAX],stanga[MAX],dreapta[MAX],hl1[MAX],hc1[MAX],hl2[MAX],hc2[MAX],l1[MAX],c1[MAX],l2[MAX],c2[MAX];

int skyline(int m, int n, int h[]){
    int vf,a,max,i,j;

    for(i=1; i<=m; i++)
        st[i]=0;
    st[0]=vf=0;
    for(j=1; j<=m; j++){
        while(vf>0 && h[j]<=h[st[vf]])
            vf--;
        stanga[j]=st[vf];
        st[++vf]=j;
    }
    for(i=1; i<=m; i++)
        st[i]=0;
    vf=0;
    st[0]=m+1;
    for(j=m; j>0; j--){
        while(vf>0 && h[j]<=h[st[vf]])
            vf--;
        dreapta[j]=st[vf];
        st[++vf]=j;
    }
    max=0;
    for(i=1; i<=m; i++){
        a=h[i]*(dreapta[i]-1-stanga[i]);
        if(a>max)
            max=a;
    }
    return max;
}

int main(){
    FILE *fin=fopen("bmatrix.in","r");
    FILE *fout=fopen("bmatrix.out","w");
    int i,j,a,max;

    fscanf(fin,"%d%d ",&m,&n);
    for(i=1; i<=m; i++){
        for(j=1; j<=n; j++)
            t[i][j]=fgetc(fin)-'0';
        fgetc(fin);
    }
    for(i=1; i<m; i++){
        for(j=1; j<=n; j++)
            if(t[i][j]==0)
                hc1[j]++;
            else
                hc1[j]=0;
        l1[i]=maxim(skyline(n,i,hc1),l1[i-1]);
    }
    for(i=1; i<n; i++){
        for(j=1; j<=m; j++)
            if(t[j][i]==0)
                hl1[j]++;
            else
                hl1[j]=0;
        c1[i]=maxim(skyline(m,i,hl1),c1[i-1]);
    }
    for(i=m-1; i>0; i--){
        for(j=n; j>0; j--)
            if(t[i+1][j]==0)
                hc2[j]++;
            else
                hc2[j]=0;
        l2[i]=maxim(skyline(n,m-i,hc2),l2[i+1]);
    }
    for(i=n-1; i>0; i--){
        for(j=m; j>0; j--)
            if(t[j][i+1]==0)
                hl2[j]++;
            else
                hl2[j]=0;
        c2[i]=maxim(skyline(m,n-i,hl2),c2[i+1]);
    }
    max=0;
    for(i=1; i<m; i++)
        if(max<l1[i]+l2[i])
            max=l1[i]+l2[i];
    for(i=1; i<n; i++)
        if(max<c1[i]+c2[i])
            max=c1[i]+c2[i];
    fprintf(fout,"%d\n",max);
    fclose(fin);
    fclose(fout);
    return 0;
}