Pagini recente » Cod sursa (job #2109499) | Cod sursa (job #1215285) | Cod sursa (job #1664628) | Cod sursa (job #761539) | Cod sursa (job #636376)
Cod sursa(job #636376)
#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;
}
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 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;
}