Cod sursa(job #636307)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 noiembrie 2011 18:37:04
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 2.15 kb
#include <cstdio>
#include <stack>

#define NMax 1005

using namespace std;

int N, M, X[NMax][NMax], Pal[NMax][NMax];
int D[NMax], Size[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=j-2; k>0; k-=2)
            {
                bool V=true;
                for (int l=0; l<=(j-k)/2; ++l)
                {
                    if (X[i][k+l]!=X[i][j-l])
                    {
                        V=false;
                        break;
                    }
                }
                if (V)
                {
                    Pal[i][j]=j-k+1;
                }
            }
        }
    }
}

void FindDS ()
{
    int TotalS=0;
    Stack.push (0);
    for (int i=1; i<=N; ++i)
    {
        while (!Stack.empty () and D[Stack.top ()]>=D[i])
        {
            TotalS-=Size[Stack.top ()];
            Stack.pop ();
        }
        TotalS+=(D[i]*(i-Stack.top ()));
        Size[i]=TotalS-Size[Stack.top ()];
        Stack.push (i);
        S=Max (S, Size[i]);
    }
    while (!Stack.empty ())
    {
        Stack.pop ();
    }
}

void Brute ()
{
    for (int i=1; i<=N; ++i)
    {
        int L=D[i];
        for (int j=i; j<=N; ++j)
        {
            if (D[j]<L)
            {
                L=D[j];
            }
            S=Max (S, L*(j-i+1));
        }
    }
}

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

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