Cod sursa(job #1367435)

Utilizator Athena99Anghel Anca Athena99 Data 1 martie 2015 21:16:01
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

const int nmax= 200;

int n, m, sol;
int x[nmax+1], y[nmax+1], a[nmax+1][nmax+1];

char v[nmax+1][nmax+1], aux[nmax+1][nmax+1];

void rotate(  ) {
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            aux[j][n-i+1]= v[i][j];
        }
    }

    n= n^m; m= n^m; n= n^m;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            v[i][j]= aux[i][j];
        }
    }
}

void solve(  ) {
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            a[i][j]= (1-(v[i][j]-'0'))*(a[i-1][j]+1);
        }
        x[i]= y[i]= 0;
    }

    for ( int i= 1; i<=n; ++i ) {
        for ( int j= i; j<=n; ++j ) {
            int aux= 0;
            for ( int k= 1; k<=m; ++k ) {
                if ( a[j][k]>=j-i+1 ) {
                    ++aux;
                } else {
                    aux= 0;
                }

                y[j]= max(y[j], aux*(j-i+1));
                x[i]= max(x[i], aux*(j-i+1));
            }
        }
    }

    for ( int i= 2; i<=n; ++i ) {
        y[i]= max(y[i], y[i-1]);
        x[n-i+1]= max(x[n-i+1], x[n-i+2]);
    }

    for ( int i= 1; i<=n-1; ++i ) {
        sol= max(sol, y[i]+x[i+1]);
    }
}

int main(  ) {
    fin>>n>>m;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i]+1;
    }

    solve();
    rotate();
    solve();

    fout<<sol<<"\n";

    return 0;
}