Cod sursa(job #990133)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 27 august 2013 15:44:30
Problema DreptPal Scor 100
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++)
        {
            P[i][j]=P[i][2*C-j];
 
            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;
}