Cod sursa(job #1164135)

Utilizator PatrikStepan Patrik Patrik Data 1 aprilie 2014 21:17:59
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
    #include<cstdio>
    #include<iostream>
    using namespace std;
    #define NMAX 201
    int N , M , h[NMAX], best , Ar , deq[NMAX] , l , r , st[NMAX] , dr[NMAX];
    char A[NMAX][NMAX+5];

    int solve(int x1 , int x2 , int y1 , int y2)
    {
        int ret = 0;
        for(int i = y1 ; i <= y2 ; ++i )
            h[i] = 0;
        h[y1-1] = h[y2+1] = -1;
        for(int i = x1 ; i <= x2 ; ++i )
        {
            for(int j = y1 ; j<= y2 ; ++j )
                if(A[i][j] == '0')h[j]++;
                else h[j] = 0;
            deq[1] = y1-1;
            l = r = 1;
            for(int j = y1 ; j <= y2 ; ++j )
            {
                while(h[j] <= h[deq[r]])r--;
                deq[++r] = j;
                st[j] = deq[r-1]+1;
            }
             l = r = 1;
             deq[1] = y2+1;
             for(int j = y2 ; j >= y1 ; j-- )
             {
                 while(h[j] <= h[deq[r]])r--;
                 deq[++r] = j;
                 dr[j] = deq[r-1]-1;
             }
             for(int j = y1 ; j <= y2 ; ++j )
                if((dr[j]-st[j]+1)*h[j] > ret)
                    ret = (dr[j]-st[j]+1)*h[j];
        }
        return ret;
    }

    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" , A[i]+1);
        for(int i = 1 ; i < M ; ++i )
            best = max(best,solve(1,N,1,i) + solve(1,N,i+1,M));
        for(int i = 1 ; i < N ; ++i )
            best = max(best,solve(1,i,1,M) + solve(i+1,N,1,M));
        printf("%d" , best);
        return 0;
    }