Cod sursa(job #1643120)

Utilizator borcanirobertBorcani Robert borcanirobert Data 9 martie 2016 17:41:05
Problema BMatrix Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAX = 210;
int a[MAX][MAX];
int D[MAX][MAX];
int t[MAX][MAX];
int unu[MAX][MAX];
int N, M;
char c;
int maxim;
int x1, y1, x2, y2;
int A, A2;

int main()
{
    int i, j, i2, jp, j2;

    fin >> N >> M;
    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
        {
            fin >> c;
            a[i][j] = c - '0';
            if ( a[i][j] ) D[i][j] = 1, t[i][j] = i, unu[i][j] = i;
            else unu[i][j] = unu[i - 1][j];
        }

    for ( i = 1; i <= N; i++ )
        for ( i2 = i + 1; i2 <= N; i2++ )
            for ( j = jp = 1; j <= M; j++ )
            {
                if ( unu[i2][j] >= i )
                {
                    jp = j + 1;
                }
                else
                    if ( ( j - jp + 1 ) * ( i2 - i + 1 ) > D[i2][j] )
                        D[i2][j] = ( j - jp + 1 ) * ( i2 - i + 1 ), t[i2][j] = i;
            }

    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            if ( D[i][j] > maxim )
            {
                if ( i == 5 && j == 6 )
                    fout << "DA";
                maxim = D[i][j];
                x2 = i, y2 = j;
                x1 = t[i][j];
                y1 = j - ( D[i][j] / ( x2 - x1 + 1 ) );
                for ( i2 = x2; i2 >= x1; i2-- )
                    A2 = max( A2, D[i2][y1] + D[i][j] );
                for ( j2 = y2; j2 >= y1; j2-- )
                    A2 = max( A2, D[x1][j2] + D[i][j] );
            }

    A = maxim;

    for ( i = x1; i <= x2; i++ )
        for ( j = y1; j <= y2; j++ )
            a[i][j] = 1;

    memset( D, 0, sizeof(D) );

    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            if ( a[i][j] ) unu[i][j] = i;
            else unu[i][j] = unu[i - 1][j];

    for ( i = 1; i <= N; i++ )
        for ( i2 = i + 1; i2 <= N; i2++ )
            for ( j = jp = 1; j <= M; j++ )
            {
                if ( unu[i2][j] >= i )
                {
                    jp = j + 1;
                }
                else
                    if ( ( j - jp + 1 ) * ( i2 - i + 1 ) > D[i2][j] )
                        D[i2][j] = ( j - jp + 1 ) * ( i2 - i + 1 ), t[i2][j] = i;
            }

    maxim = 0;
    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            maxim = max( maxim, D[i][j] );

    fout << max(A + maxim, A2) << '\n';

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