Pagini recente » Cod sursa (job #993167) | Cod sursa (job #3147853) | Cod sursa (job #2344057) | Cod sursa (job #2689235) | Cod sursa (job #2595880)
#include<fstream>
#include<stack>
#include<algorithm>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m,a[1002][1002],manacher[1002][1002];
stack<int>s;
void Manacher(int x)
{
int i,st,dr,poz=0,l=0,ll;
for(i=1;i<=m;i++)
{
if(i>poz+l)
{
poz=i;
l=0;
st=i-1;
dr=i+1;
while(st>=1&&dr<=m&&a[x][st]==a[x][dr])
{
st--;
dr++;
l++;
}
manacher[x][i]=l;
}
else
{
if(i+manacher[x][2*poz-i]<poz+l)
manacher[x][i]=manacher[x][2*poz-i];
else
if(i+manacher[x][2*poz-i]>poz+l)
manacher[x][i]=poz+l-i;
else
{
st=i-manacher[x][2*poz-i]-1;
dr=poz+l+1;
ll=0;
while(st>=1&&dr<=m&&a[x][st]==a[x][dr])
{
st--;
dr++;
ll++;
}
manacher[x][i]=poz+l-i;
if(ll!=0)
{
manacher[x][i]+=ll;
poz=i;
l=manacher[x][i];
}
}
}
}
}
int main()
{
int i,j,sol=0,x,y;
f>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
f>>a[i][j];
Manacher(i);
}
for(j=1;j<=m;j++)
{
for(i=1;i<=n;i++)
{
while(!s.empty()&&manacher[s.top()][j]>manacher[i][j])
{
x=manacher[s.top()][j];
s.pop();
if(s.empty())
y=0;
else
y=s.top();
sol=max(sol,(2*x+1)*(i-y-1));
}
s.push(i);
}
while(!s.empty())
{
x=manacher[s.top()][j];
s.pop();
if(s.empty())
y=0;
else
y=s.top();
sol=max(sol,(2*x+1)*(n-y));
}
}
g<<sol;
return 0;
}