Pagini recente » Cod sursa (job #1862397) | Cod sursa (job #2111255) | Cod sursa (job #1309134) | Cod sursa (job #820682) | Cod sursa (job #642008)
Cod sursa(job #642008)
#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;
}