Cod sursa(job #1259056)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 9 noiembrie 2014 17:48:38
Problema BMatrix Scor 24
Compilator c Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <stdio.h>
#define MAXN 200
int m[MAXN][MAXN], L[MAXN+1], C[MAXN+1], l[MAXN], c[MAXN], stiva[MAXN], a[MAXN][MAXN], poz[MAXN];
int main(){
    int nrlin, nrcol, i, j, max, n;
    FILE *fin, *fout;
    fin=fopen("bmatrix.in", "r");
    fout=fopen("bmatrix.out", "w");
    fscanf(fin, "%d%d", &nrlin, &nrcol);
    for(i=0; i<nrlin; i++){
        fgetc(fin);
        for(j=0; j<nrcol; j++){
            m[i][j]=fgetc(fin);
        }
    }
    for(j=nrcol-1; j>=0; j--){
        for(i=0; i<nrlin; i++){
            if(m[i][j]=='1'){
                c[i]=0;
            }else{
                c[i]++;
            }
        }
        max=0;
        n=0;
        for(i=0; i<nrlin; i++){
            while((n>0)&&(c[i]<=stiva[n-1])){
                n--;
            }
            if(n>0){
                if(max<(i-poz[n-1])*c[i]){
                    max=(i-poz[n-1])*c[i];
                }
            }else{
                if(max<(i+1)*c[i]){
                    max=(i+1)*c[i];
                }
            }
            poz[n]=i;
            stiva[n]=c[i];
            n++;
        }
        C[j]=max;
    }
    for(i=nrlin-1; i>=0; i--){
        for(j=0; j<nrcol; j++){
            if(m[i][j]=='1'){
                l[j]=0;
            }else{
                l[j]++;
            }
        }
        max=0;
        n=0;
        for(j=0; j<nrcol; j++){
            while((n>0)&&(l[j]<=stiva[n-1])){
                n--;
            }
            if(n>0){
                if(max<(j-poz[n-1])*l[j]){
                    max=(j-poz[n-1])*l[j];
                }
            }else{
                if(max<(j+1)*l[j]){
                    max=(j+1)*l[j];
                }
            }
            poz[n]=j;
            stiva[n]=l[j];
            n++;
        }
        L[i]=max;
    }
    for(j=0; j<nrcol; j++){
        l[j]=0;
    }
    for(i=0; i<nrlin; i++){
        for(j=0; j<nrcol; j++){
            if(m[i][j]=='1'){
                l[j]=0;
            }else{
                l[j]++;
            }
        }
        max=0;
        n=0;
        for(j=0; j<nrcol; j++){
            while((n>0)&&(l[j]<=stiva[n-1])){
                n--;
            }
            if(n>0){
                if(max<(j-poz[n-1])*l[j]){
                    max=(j-poz[n-1])*l[j];
                }
            }else{
                if(max<(j+1)*l[j]){
                    max=(j+1)*l[j];
                }
            }
            a[i][j]=max;
            poz[n]=j;
            stiva[n]=l[j];
            n++;
        }
    }
    for(i=0; i<nrlin; i++){
        for(j=0; j<nrcol; j++){
            if(max<a[i][j]+L[i+1]){
                max=a[i][j]+L[i+1];
            }
            if(max<a[i][j]+C[j+1]){
                max=a[i][j]+C[j+1];
            }
        }
    }
    fprintf(fout, "%d\n", max);
    fclose(fin);
    fclose(fout);
    return 0;
}