Mai intai trebuie sa te autentifici.

Cod sursa(job #202480)

Utilizator dgoldenAlex Popescu dgolden Data 8 august 2008 23:34:06
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.9 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "bmatrix.in"
#define FOUT "bmatrix.out"
#define MAX_N 210

int A[MAX_N][MAX_N];
int mn[MAX_N][MAX_N];

short up[MAX_N][MAX_N];
short dwn[MAX_N][MAX_N];
short lft[MAX_N][MAX_N];
short rgt[MAX_N][MAX_N];

int N, M;
int BEST; // solutia

    inline int MIN (int a, int b)
    {
           if (a < b) return a; else return b; 
    }
   
    void preproc ()
    {
         int i, j;

         for (j = 1; j <= M; ++j)
             for (i = 1; i <= N; ++i)
                 if (A[i][j]) up[i][j] = up[i - 1][j] + 1;
                 
         for (j = 1; j <= M; ++j)
             for (i = N; i; --i)
                 if (A[i][j]) dwn[i][j] = dwn[i + 1][j] + 1;
                 
         for (i = 1; i <= N; ++i)
             for (j = 1; j <= M; ++j)
                 if (A[i][j]) lft[i][j] = lft[i][j - 1] + 1;
                 
         for (i = 1; i <= N; ++i)
             for (j = M; j; --j)
                 if (A[i][j]) rgt[i][j] = rgt[i][j + 1] + 1;
    }
    
    void solve ()
    {
         int i, j, lin, col;
         
         // baleiez liniile
         for (lin = 1; lin <= N; ++lin)
         {
             int B1, B2;
             B1 = B2 = 0;
             for (i = 1; i <= M; ++i)
                 mn[i][i] = up[lin][i];
             for (i = 1; i < M; ++i)
                 for (j = i + 1; j <= M; ++j)
                     mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
             
             for (i = 1; i < M; ++i)
                 for (j = i + 1; j <= M; ++j)
                     if (mn[i][j] * (j - i + 1) > B1)
                        B1 = mn[i][j] * (j - i + 1);
                        
             for (i = 1; i <= M; ++i)
                 mn[i][i] = dwn[lin + 1][i];
             for (i = 1; i < M; ++i)
                 for (j = i + 1; j <= M; ++j)
                     mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
             
             for (i = 1; i < M; ++i)
                 for (j = i + 1; j <= M; ++j)
                     if (mn[i][j] * (j - i + 1) > B2)
                        B2 = mn[i][j] * (j - i + 1);
                        
             if (B1 + B2 > BEST) BEST = B1 + B2;   
         }
         
         //baleiez coloanele
         for (col = 1; col <= M; ++col)
         {
             int B1, B2;
             B1 = B2 = 0;
             for (i = 1; i <= N; ++i)
                 mn[i][i] = lft[i][col];
             for (i = 1; i < N; ++i)
                 for (j = i + 1; j <= N; ++j)
                     mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
             
             for (i = 1; i < N; ++i)
                 for (j = i + 1; j <= N; ++j)
                     if (mn[i][j] * (j - i + 1) > B1)
                        B1 = mn[i][j] * (j - i + 1);
                        
             for (i = 1; i <= N; ++i)
                 mn[i][i] = rgt[i][col + 1];
             for (i = 1; i < N; ++i)
                 for (j = i + 1; j <= N; ++j)
                     mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
             
             for (i = 1; i < N; ++i)
                 for (j = i + 1; j <= N; ++j)
                     if (mn[i][j] * (j - i + 1) > B2)
                        B2 = mn[i][j] * (j - i + 1);
                        
             if (B1 + B2 > BEST) BEST = B1 + B2;   
         }

    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d\n", &N, &M);
        
        int i, j;
        for (i = 1; i <= N; ++i)
        {
            char S[250] = "";
            gets (S);
            for (j = 1; j <= M; ++j)
                A[i][j] = S[j - 1] - '0', A[i][j] = 1 - A[i][j];
        }                
               
        preproc (); 
        solve ();      
                   
        printf ("%d\n", int (BEST));
        
        return 0;
    }