Cod sursa(job #1556641)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 25 decembrie 2015 16:04:30
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[210][210],rectangle[210][210],n,m,answer=0;
void maximum_rectangle(){
    int i1,i2,j,l,lmax;
    bool v[210];
    for(i1=1;i1<=n;i1++){
        memset(v,true,sizeof(v));
        for(i2=i1;i2<=n;i2++){
            for(j=1;j<=m;j++)
                v[j]=(v[j]&a[i2][j]);
            l=0;
            lmax=-1;
            for(j=1;j<=m;j++)
                if(v[j]==1)
                    l++;
                else{
                    if(l>lmax)
                        lmax=l;
                    l=0;
                }
            if(l>lmax)
                lmax=l;
            rectangle[i1][i2]=(i2-i1+1)*lmax;
        }
    }
}
void compute_answer(){
    int i,i1,i2,max1,max2;
    for(i=1;i<=n;i++){
        max1=-1,max2=-1;
        for(i1=1;i1<=i;i1++)
            for(i2=i1;i2<=i;i2++)
                if(rectangle[i1][i2]>max1)
                    max1=rectangle[i1][i2];
        for(i1=i+1;i1<=n;i1++)
            for(i2=i1;i2<=n;i2++)
                if(rectangle[i1][i2]>max2)
                    max2=rectangle[i1][i2];
        if(max1+max2>answer)
            answer=max1+max2;
    }
}
void reverse_matrix(){
    int i,j;
    memset(rectangle,0,sizeof(rectangle));
    for(i=1;i<=200;i++)
        for(j=1;j<=200;j++)
            swap(a[i][j],a[j][i]);
    swap(n,m);
}
int main(){
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int i,j;
    char enter,ch;
    scanf("%d%d%c",&n,&m,&enter);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%c",&ch);
            a[i][j]=ch-'0';
            a[i][j]=1-a[i][j];
        }
        scanf("%c",&enter);
    }
    maximum_rectangle();
    compute_answer();
    reverse_matrix();
    maximum_rectangle();
    compute_answer();
    printf("%d",answer);
    return 0;
}