Cod sursa(job #1386789)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 martie 2015 11:36:43
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define Nmax 210

using namespace std;

int n , m , i , j , k , Max[3] , Lf[3] , Ls[3] , Cf[3] , Cs[3];

int A[Nmax][Nmax] , H[Nmax] , l[Nmax] , q[Nmax];

char s[Nmax];

void dreptunghi()
{
    int kk , nn , cnt;
    for (cnt = 1; cnt <= 2; ++cnt)
    {
         //memset(H , 0 , sizeof(H));
         for (Max[cnt] = 0 , kk = Lf[cnt]; kk <= Ls[cnt]; ++kk)
         {
             for (j = Cf[cnt]; j <= Cs[cnt]; ++j)
              if (kk == Lf[cnt]) H[j] = (A[kk][j] == 1) ? 1 : 0;
              else H[j] = (A[kk][j] == 1) ? H[j] + 1 : 0;

              //memset(l , 0 , sizeof(l));
              //for (j = Cf[cnt] - 1; j <= Cs[cnt] + 1; ++j) l[j] = 0;

              H[Cf[cnt]-1] = -1; q[Cf[cnt]-1] = nn = Cf[cnt]-1;

              for (i = Cf[cnt]; i <= Cs[cnt]; ++i)
              {
                  j = nn;
                  while (H[q[j]] >= H[i]) --j;

                  nn = ++j; l[i] = i - q[j-1]; q[j]=i;
              }

              H[Cs[cnt]+1] = -1; q[Cf[cnt]-1] = Cs[cnt] + 1; nn = Cf[cnt]-1;

              for (i = Cs[cnt]; i > Cf[cnt] - 1; --i)
              {
                  j = nn;
                  while (H[q[j]] >= H[i]) --j;

                  nn = ++j; l[i] += q[j-1] - i - 1; q[j] = i;

                  Max[cnt] = max(Max[cnt] , l[i] * H[i]);
              }
        }
    }

    Max[0] = max(Max[0] , Max[1] + Max[2]);
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);

    scanf("%d %d\n", &n, &m);

    for (i = 1; i <= n; ++i)
    {
        gets(s+1);

        for (j = 1; j <= m; ++j)
         A[i][j] = (s[j] == '0');
    }

    for (k = 1; k <= n; ++k)
    {
        /// prima matrice (1,1) - (k,m)
        /// a doua matrice (k+1,1) - (n,m)

        Lf[1] = 1; Ls[1] = k; Cf[1] = 1; Cs[1] = m;

        Lf[2] = k + 1; Ls[2] = n; Cf[2] = 1; Cs[2] = m;

        dreptunghi();
    }

    for (k = 1; k <= m; ++k)
    {
        /// prima matrice (1,1) - (n,k)
        /// a doua matrice (1,k+1) - (n,m)

        Lf[1] = 1; Ls[1] = n; Cf[1] = 1; Cs[1] = k;

        Lf[2] = 1; Ls[2] = n; Cf[2] = k + 1; Cs[2] = m;

        dreptunghi();
    }

    printf("%d\n", Max[0]);

    return 0;
}