Cod sursa(job #1387945)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 14 martie 2015 21:33:23
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define Nmax 210

using namespace std;

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

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

char A[Nmax][Nmax];

void dreptunghi()
{
    int kk , nn , cnt , start , finish;
    for (cnt = 1; cnt <= 2; ++cnt)
    {
        int t = 0;
        for (i = Lf[cnt]; i <= Ls[cnt]; ++i)
            for (j = Cf[cnt]; j <= Cs[cnt]; ++j)
                H[++t][cnt] = (A[i][j] == '0') ? H[t][cnt] + 1 : 0;

        if (Lf[cnt] == Ls[cnt]) start = Cf[cnt] , finish = Cs[cnt];
        else start = Lf[cnt] , finish = Ls[cnt];

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

        for (i = start; i <= finish; ++i)
        {
            for (j = nn; H[q[j]][cnt] >= H[i][cnt]; --j);

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

        H[finish+1][cnt] = -1; q[start-1] = finish + 1; nn = start-1;

        for (Max[k][cnt] = Max[k-1][cnt] , i = finish; i >= start; --i)
        {
            for (j = nn; H[q[j]][cnt] >= H[i][cnt]; --j);

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

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

        }

    }
}

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(A[i]+1);


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

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

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

        dreptunghi();
    }

    for (i = 1; i <= n; ++i)
      sol = max(sol , Max[i][1] + Max[n-i][2]),
      Max[i][1] = Max[n-i][2] = 0;

    for (j = 1; j <= m; ++j)
        H[j][1] = H[j][2] = 0;

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

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

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

        dreptunghi();
    }

    for (i = 1; i <= m; ++i)
        sol = max(sol , Max[i][1] + Max[m-i][2]);

    printf("%d\n", sol);

    return 0;
}