Cod sursa(job #1164242)

Utilizator PatrikStepan Patrik Patrik Data 1 aprilie 2014 22:52:02
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
    #include<cstdio>
    #include<iostream>
    using namespace std;
    #define NMAX 205
    int h[NMAX][NMAX] , st[NMAX][NMAX] , dr[NMAX][NMAX] , dq[NMAX];
    int n , m , l , r , best ;
    char s[NMAX][NMAX] , s1[NMAX][NMAX];

    int solve1(int x1 , int x2 , int y1 , int y2)
    {
        int ret = 0;
        for(int i = x1 ; i <= x2 ; ++i )
            for(int j = y1 ; j <= y2 ; ++j )
                ret = max(ret,h[i][j]*(min(dr[i][j],y2)-max(st[i][j],y1)+1));
        return ret;
    }

    void solve( char s[NMAX][NMAX],int N , int M);

    int main()
    {
        freopen("bmatrix.in" , "r" , stdin );
        freopen("bmatrix.out" , "w" , stdout );
        scanf("%d%d" , &n , &m );
        for(int i = 1 ; i<= n ; ++i )
            scanf("%s" , s[i]+1);
        for(int i = 1 ; i<= n ; ++i )
            for(int j = 1 ; j <= m ; ++j )
                s1[j][i] = s[i][j];
        solve(s,n,m);
        solve(s1,m,n);
        printf("%d\n" , best);
        return 0;
    }

    void solve(char s[NMAX][NMAX] ,int  N ,int  M )
    {
        for(int i = 1 ; i <= N ; ++i )
        {
            h[i][0] = h[i][M+1] = -1;
            for(int j  = 1 ; j <= M ; ++j )
                if(s[i][j] == '0')h[i][j] = h[i-1][j]+1;
                else h[i][j] = 0;

            dq[1] = 0;
            l = r = 1;
            for(int j = 1 ; j <= M ; ++j )
            {
                while(h[i][j] <= h[i][dq[r]])r--;
                dq[++r] = j;
                st[i][j] = dq[r-1]+1;
            }
            dq[1] = M+1;
            l = r = 1;
            for(int j = M ; j ; j--)
            {
                while(h[i][j] <= h[i][dq[r]])r--;
                dq[++r] = j;
                dr[i][j] = dq[r-1]-1;
            }
        }

        for(int i = 1 ; i < M ; ++i )
            best = max(best,solve1(1,N,1,i) + solve1(1,N,i+1,M));
    }