Cod sursa(job #642008)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 30 noiembrie 2011 12:47:34
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 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;
}

inline int Min (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)
    {
        int P=0, R=0;
        for (int j=1; j<=M; ++j)
        {
            if (P+R>=j)
            {
                Pal[i][j]=Min ((Pal[i][P-(j-P)]-1)/2, R-j);
            }
            for (int k=Pal[i][j]+1; j+k<=M and j-k>0; ++k)
            {
                if (X[i][j+k]==X[i][j-k])
                {
                    ++Pal[i][j];
                }
                else
                {
                    break;
                }
            }
            if (j+Pal[i][j]>R)
            {
                R=j+Pal[i][j];
                P=j;
            }
            Pal[i][j]*=2;
            ++Pal[i][j];
        }
    }
}

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;
}