Cod sursa(job #1112045)

Utilizator poptibiPop Tiberiu poptibi Data 19 februarie 2014 13:00:42
Problema BMatrix Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;

const int NMAX = 210, INF = 0x3f3f3f3f;

int N, M, Mat[NMAX][NMAX], Up[NMAX][NMAX], Down[NMAX][NMAX], Left[NMAX], Right[NMAX];
int MaxUp[NMAX], MaxDown[NMAX], Ans, Aux[NMAX][NMAX];
char S[NMAX][NMAX];

void RotateMatrix()
{
    int Line = 1, Col = 1;
    for(int i = 1; i <= N; ++ i, Line = 1, ++ Col)
        for(int j = 1; j <= M; ++ j, ++ Line)
        {
            Aux[Line][Col] = Mat[i][j];
            Mat[i][j] = Up[i][j] = Down[i][j] = 0;
        }
    swap(N, M);
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            Mat[i][j] = Aux[i][j];
}

void Solve()
{
    for(int i = 1; i <= N; ++ i)
        MaxUp[i] = MaxDown[i] = 0;

    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            Up[i][j] = (1 - Mat[i][j]) * (Up[i - 1][j] + 1);
    for(int i = N; i; -- i)
        for(int j = 1; j <= M; ++ j)
            Down[i][j] = (1 - Mat[i][j]) * (Down[i + 1][j] + 1);

    for(int i = 1; i <= N; ++ i)
    {
        stack<int> S;
        Up[i][0] = Up[i][M + 1] = Down[i][0] = Down[i][M + 1] = -INF;
        S.push(0);

        for(int j = 1; j <= M; ++ j)
        {
            while(!S.empty() && Up[i][S.top()] >= Up[i][j]) S.pop();
            Left[j] = S.top() + 1;
            S.push(j);
        }

        while(!S.empty()) S.pop();
        S.push(M + 1);

        for(int j = M; j; -- j)
        {
            while(!S.empty() && Up[i][S.top()] >= Up[i][j]) S.pop();
            Right[j] = S.top() - 1;
            S.push(j);
        }
        for(int j = 1; j <= M; ++ j)
            MaxUp[i] = max(MaxUp[i], Up[i][j] * (Right[j] - Left[j] + 1));
        MaxUp[i] = max(MaxUp[i], MaxUp[i - 1]);

        while(!S.empty()) S.pop();
        S.push(0);

        for(int j = 1; j <= M; ++ j)
        {
            while(!S.empty() && Down[i][S.top()] >= Down[i][j]) S.pop();
            Left[j] = S.top() + 1;
            S.push(j);
        }

        while(!S.empty()) S.pop();
        S.push(M + 1);

        for(int j = M; j; -- j)
        {
            while(!S.empty() && Down[i][S.top()] >= Down[i][j]) S.pop();
            Right[j] = S.top() - 1;
            S.push(j);
        }

        for(int j = 1; j <= M; ++ j)
            MaxDown[i] = max(MaxDown[i], Down[i][j] * (Right[j] - Left[j] + 1));
    }

    for(int i = 1; i < N; ++ i)
        Ans = max(Ans, MaxUp[i] + MaxDown[i + 1]);
}

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

    scanf("%i %i\n", &N, &M);
    for(int i = 1; i <= N; ++ i)
    {
        gets(S[i] + 1);
        for(int j = 1; j <= M; ++ j)
            Mat[i][j] = S[i][j] - '0';
    }

    Solve();
    RotateMatrix();
    Solve();

    printf("%i\n", Ans);
}