Cod sursa(job #1662210)

Utilizator borcanirobertBorcani Robert borcanirobert Data 24 martie 2016 16:22:20
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAX = 210;
int D[MAX][MAX];
int a[MAX][MAX];
int N, M;
int sol;

void Maxime();
void Sol();
void Rotate();

int main()
{
    int i, j, l1, l2;
    char c;

    fin >> N >> M;
    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
        {
            fin >> c;
            a[i][j] = c - '0';
        }

    Maxime();
    Sol();
    Rotate();
    Maxime();
    Sol();

    fout << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Maxime()
{
    int l1, l2, c, lmax;
    bool e[MAX];
    for ( l1 = 1; l1 <= N; l1++ )
    {
        memset( e, 1, sizeof(e) );
        for ( l2 = l1; l2 <= N; l2++ )
        {
            lmax = 0;
            for ( c = 1; c <= M; c++ )
                if ( a[l2][c] == 1 )
                    e[c] = 0;

            int l = 0;
            for ( c = 1; c <= M; c++ )
            {
                if ( e[c] == 1 ) l++;
                else l = 0;
                lmax = max( l, lmax );
            }
            D[l1][l2] = lmax * ( l2 - l1 + 1 );
        }
    }
}

void Sol()
{
    int mij, l1, l2;
    int m1, m2;

    for ( mij = 1; mij <= N; mij++ )
    {
        m1 = m2 = 0;
        for ( l1 = 1; l1 <= mij; l1++ )
            for ( l2 = l1 + 1; l2 <= mij; l2++ )
                m1 = max( m1, D[l1][l2] );

        for ( l1 = mij + 1; l1 <= N; l1++ )
            for ( l2 = l1 + 1; l2 <= N; l2++ )
                m2 = max( m2, D[l1][l2] );

        sol = max( sol, m1 + m2 );
    }
}

void Rotate()
{
    int i, j;
    int aux[MAX][MAX];
    int L = MAX - 4;

    memset( aux, 0, sizeof(aux) );

    for ( i = 1; i <= L; i++ )
        for ( j = 1; j <= L; j++ )
            aux[i][j] = a[j][i];

    for ( i = 1; i <= L; i++ )
        for ( j = 1; j <= L; j++ )
            a[i][j] = aux[i][j];

    swap(N, M);
}