Pagini recente » Cod sursa (job #2487149) | Cod sursa (job #2880617) | Cod sursa (job #2962212) | Cod sursa (job #3200809) | Cod sursa (job #636301)
Cod sursa(job #636301)
#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=j-2; k>0; k-=2)
{
for (int l=0; l<(j-k)/2; ++l)
{
if (X[i][k+l]!=X[i][j-l])
{
break;
}
if (l==(j-k)/2-1)
{
Pal[i][j]=j-k+1;
}
}
}
}
}
}
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 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;
}