Pagini recente » Cod sursa (job #3198202) | Cod sursa (job #1536893) | Cod sursa (job #1809163) | Cod sursa (job #2370802) | Cod sursa (job #1391398)
#include <fstream>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int N,M,Matrix[1005][1005],DP[1005][1005],Stack[1005],Left[1005],Right[1005];
int ans;
int Expand(int Left,int Right,int line)
{
int length=0;
while(Left>=1 && Right<=M && Matrix[line][Left]==Matrix[line][Right])
{
length++;
Left--;
Right++;
}
return length;
}
void precalcDP(int line)
{
int i,R=0,P=0,Left,Right;
for(i=1;i<=M;i++)
{
if(R>=i)
DP[line][i]=min(R-i,DP[line][P-(i-P)]);
Left=i-DP[line][i];
Right=i+DP[line][i];
DP[line][i]+=Expand(Left,Right,line);
if(DP[line][i]+i>R)
{
R=DP[line][i]+i;
P=i;
}
}
}
void Read()
{
f>>N>>M;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
f>>Matrix[i][j];
for(int i=1;i<=N;i++)
precalcDP(i);
}
void precalcLeft(int col)
{
Stack[0]=0;
for(int j=N;j>=1;j--)
{
while(Stack[0]!=0 && DP[Stack[Stack[0]]][col]>DP[j][col])
{
Left[Stack[Stack[0]]]=j;
--Stack[0];
}
Stack[++Stack[0]]=j;
}
}
void precalcRight(int col)
{
Stack[0]=0;
for(int j=1;j<=N;j++)
{
Right[j]=N+1;
while(Stack[0]!=0 && DP[Stack[Stack[0]]][col]>DP[j][col])
{
Right[Stack[Stack[0]]]=j;
--Stack[0];
}
Stack[++Stack[0]]=j;
}
}
void countResult()
{
for(int i=1;i<=M;i++)
{
precalcLeft(i);
precalcRight(i);
for(int j=1;j<=N;j++)
ans=max(ans,(Right[j]-Left[j]-1)*(2*DP[j][i]-1));
}
g<<ans<<"\n";
}
int main()
{
Read();
countResult();
return 0;
}