Pagini recente » Cod sursa (job #400044) | Cod sursa (job #1386347) | Cod sursa (job #3197759) | Cod sursa (job #3203238) | Cod sursa (job #1867240)
#include <iostream>
#include <fstream>
#define DM 1002
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m, i, j, t[DM][DM*2], jj, r, c, st[DM], stpoz[DM], top, val, nr, aria;
short lps[DM][DM*2];
bool ok, expand;
void Manacher()//caz general
{
m=2*m+1;
//aplicam algoritmul lui Manacher pe fiecare linie
for(i=1;i<=n;i++)
{
lps[i][1]=c=1;
r=2;
for(j=2;j<=m;j++)
{
expand=0;
jj=2*c-j;
if(j>=r)
expand=1;
else
{
if(lps[i][jj]<=r-j)
lps[i][j]=lps[i][jj];
if(lps[i][jj]==r-j)
expand=1;
if(lps[i][jj]>r-j)
{
lps[i][j]=r-j;
expand=1;
}
}
if(expand)
{
ok=1;
while(j-lps[i][j]>0 && j+lps[i][j]<m && ok)
{
if((j-lps[i][j]-1)%2==0)
lps[i][j]++;
else
{
if(t[i][j-lps[i][j]-1] == t[i][j+lps[i][j]+1])
lps[i][j]++;
else ok=0;
}
}
}
if(lps[i][j]>r)
{
c=j;
r=j+lps[i][j];
}
}
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=n;i++)
{
t[i][0]=-1;
for(j=1;j<=m;j++)
{
fin>>t[i][2*j-1];
t[i][2*j]=-1;
}
}
Manacher();
for(j=1;j<m;j++)
if(j%2!=0)
{
for(i=1;i<=n;i++)
{
val=lps[i][j];
if(top==0 || val>st[top])
{
top++;
st[top]=val;
stpoz[top]=i;
}
else
{
int last=i;
while(top>0 && val<=st[top])
{
last=stpoz[top];
aria=max(aria,(i-stpoz[top])*st[top]);
top--;
}
top++;
st[top]=val;
stpoz[top]=last;
}
}
while(top>0)
{
aria=max(aria,(n-stpoz[top])*st[top]);
top--;
}
}
fout<<aria;
return 0;
}