Cod sursa(job #636330)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 noiembrie 2011 18:54:03
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 2 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=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 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;
}