Cod sursa(job #864476)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 25 ianuarie 2013 00:09:33
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <stack>
#define NM 1010

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int N, M;
int i, j;
int A[NM][NM];
int P[NM][NM];
int U[NM], D[NM];
int C, R;
int ANS;
stack<int> S;

void Clear ()
{
    while (!S.empty()) S.pop();
}

int main ()
{
    f >> N >> M;
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            f >> A[i][j];

    for (i=1; i<=N; i++)
    {
        C=R=0;

        for (j=1; j<=M; j++)
        {
            if (j<=R)
                P[i][j]=P[i][2*C-i];

            while (1<=j-P[i][j] && j+P[i][j]<=M && A[i][j-P[i][j]]==A[i][j+P[i][j]]) P[i][j]++;
            P[i][j]--;

            if (j+P[i][j]>R)
            {
                C=j;
                R=j+P[i][j];
            }
        }

        for (j=1; j<=M; j++)
            P[i][j]=1+2*P[i][j];
    }

    for (j=1; j<=M; j++)
    {
       S.push(0);
       P[0][j]=-1;

       for (i=1; i<=N; i++)
       {
           while (!S.empty() && P[S.top()][j]>=P[i][j]) S.pop();

           U[i]=S.top()+1;

           S.push(i);
       }

       Clear();
       S.push(N+1);
       P[N+1][j]=-1;

        for (i=N; i>=1; i--)
       {
           while (!S.empty() && P[S.top()][j]>=P[i][j]) S.pop();

           D[i]=S.top()-1;

           S.push(i);

           ANS=max(ANS, P[i][j]*(D[i]-U[i]+1));
       }

       Clear();
    }

    g << ANS << '\n';

    f.close();
    g.close();

    return 0;
}