Cod sursa(job #636376)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 noiembrie 2011 19:28:06
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 2.12 kb
#include <cstdio>
#include <stack>

#define NMax 1005

using namespace std;

int N, M, X[NMax][NMax], Pal[NMax][NMax];
int D[NMax], Left[NMax], Right[NMax], S;
stack <int> Stack;

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

void Read ()
{
    freopen ("dreptpal.in", "r", stdin);
    scanf ("%d %d", &N, &M);
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            scanf ("%d", &X[i][j]);
        }
    }
}

void Print ()
{
    freopen ("dreptpal.out", "w", stdout);
    printf ("%d\n", S);
}

void BuildM ()
{
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            Pal[i][j]=1;
            for (int k=1; j+k<=M and j-k>0; ++k)
            {
                if (X[i][j+k]==X[i][j-k])
                {
                    Pal[i][j]+=2;
                }
                else
                {
                    break;
                }
            }
        }
    }
}

void BuildLeft ()
{
    for (int i=1; i<=N; ++i)
    {
        int Last=i;
        while (!Stack.empty () and D[Stack.top ()]>D[i])
        {
            Last=Left[Stack.top ()];
            Stack.pop ();
        }
        Left[i]=Last;
        Stack.push (i);
    }
    while (!Stack.empty ())
    {
        Stack.pop ();
    }
}

void BuildRight ()
{
    for (int i=N; i>0; --i)
    {
        int Last=i;
        while (!Stack.empty () and D[Stack.top ()]>=D[i])
        {
            Last=Right[Stack.top ()];
            Stack.pop ();
        }
        Right[i]=Last;
        Stack.push (i);
    }
    while (!Stack.empty ())
    {
        Stack.pop ();
    }
}

void FindDS ()
{
    BuildLeft ();
    BuildRight ();
    for (int i=1; i<=N; ++i)
    {
        S=Max (S, (Right[i]-Left[i]+1)*D[i]);
    }
}

void Solve ()
{
    BuildM ();
    for (int j=1; j<=M; ++j)
    {
        for (int i=1; i<=N; ++i)
        {
            D[i]=Pal[i][j];
        }
        FindDS ();
    }
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}