Cod sursa(job #74236)

Utilizator vlad_popaVlad Popa vlad_popa Data 24 iulie 2007 12:33:28
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.16 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>

#define NMAX 201
#define FIN "bmatrix.in"
#define FOUT "bmatrix.out"
#define INF 0x3f3f3f3f

int N, M, Line[NMAX][NMAX], Col[NMAX][NMAX], A[NMAX][NMAX];
int Ls[NMAX], Lj[NMAX], Cst[NMAX], Cdr[NMAX];

void read ()
{
    scanf ("%d %d\n", &N, &M);
    
    int temp;
    char x;
    for (int i = 1; i <= N; ++ i)
    {
        temp = 0;
        for (int j = 1; j <= M; ++ j)
        {
            scanf ("%c", &x);
            x != '0' ? temp = 0: ++ temp;
            if (!temp)
                Col[i][j] = temp;
            else
                Col[i][j] = Col[i-1][j] + 1;    
            Line[i][j] = temp; 
        }
        scanf ("\n");
    }                            
}

int dinamicaL (int bx, int by, int ex, int ey, int p)
{
    int Max, Min, poz, sol = 0;
    
    if (!p)
    {
        poz = ex;
        for (int j = by; j <= ey; ++ j)
        {
            Min = INF;
            Max = 0;
            if (Line[poz][j])
                for (int i = poz; i >= bx; -- i)
                {
                    Min = min (Min, Line[i][j]);
                    //printf ("%d %d %d\n", Min * (poz - i + 1), Min, poz, i);
                    Max = max (Min * (poz - i + 1), Max);                    
                }
            sol = max (sol, Max);
        }
                
        return sol;
    }
    else
    {
        poz = bx;
        for (int j = by; j <= ey; ++ j)
        {
            Min = INF;
            Max = 0;
            if (Line[poz][j])
                for (int i = poz; i <= ex; ++ i)
                {
                    Min = min (Min, Line[i][j]);
                    Max = max (Min * (i - poz + 1), Max);
                }
            sol = max (sol, Max);    
        }
                
        return sol;                
    }
}

int dinamicaC (int bx, int by, int ex, int ey, int p)
{
    int Max = 0, Min, poz, sol = 0;
    
    if (!p)
    {
        poz = ey;
        for (int i = bx; i <= ex; ++ i)
        {
            Min = INF;
            Max = 0;
            if (Col[i][poz])
                for (int j = poz; j >= by; -- j)
                {
                    Min = min (Min, Col[i][j]);
                    Max = max (Min * (poz - j + 1), Max);                    
                }
            sol = max (sol, Max);    
        }
                
        return sol;
    }
    else
    {
        poz = by;
        for (int i = bx; i <= ex; ++ i)
        {
            Min = INF;
            Max = 0;
            if (Col[i][poz])
                for (int j = poz; j <= ey; ++ j)
                {
                    Min = min (Min, Col[i][j]);
                    Max = max (Min * (j - poz + 1), Max);
                }
            sol = max (sol, Max);
        }
                
        return sol;                
    }
}

void solve ()
{
    int Max = 0, sol = 0;
    
    for (int poz = 1; poz <= N; ++ poz)
    {
        Ls[poz] = dinamicaL (1, 1, poz, M, 0);
        Lj[poz] = dinamicaL (poz, 1, N, M, 1);
    }
    
    for (int poz = 1; poz <= M; ++ poz)
    {
        Cst[poz] = dinamicaC (1, 1, N, poz, 0);
        Cdr[poz] = dinamicaC (1, poz, N, M, 1);
    }
    
    /*for (int i = 1; i <= M; ++ i)
        printf ("%d ", Cst[i]);
    printf ("\n");
    for (int i = 1; i <= M; ++ i)
        printf ("%d ", Cdr[i]);
    printf ("\n");    */
    
    for (int i = 1; i < N; ++ i)
    {
        Max = 0;
        for (int j = i + 1; j <= N; ++ j)
            if (Max < Lj[j])
                Max = Lj[j];
        
        if (sol < Max + Ls[i])
            sol = Max + Ls[i];
    }
    
    for (int i = 1; i < M; ++ i)
    {
        Max = 0;
        for (int j = i + 1; j <= M; ++ j)
            if (Max < Cdr[j])
                Max = Cdr[j];
        
        if (sol < Max + Cst[i])
            sol = Max + Cst[i];
    }
    
    printf ("%d\n", sol);
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);
      
    read ();
    solve ();
      
    return 0;
}