Pagini recente » Cod sursa (job #2982473) | Cod sursa (job #2892982) | Cod sursa (job #2557921) | Cod sursa (job #2216913) | Cod sursa (job #2761005)
#include <bits/stdc++.h>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m;
int v[1005][1005],manacher[1005][1005];
int aux[1005],st[1005],dr[1005],stiva[1005];
int ans=0;
void compute_manacher(int ind)
{
int l=0,r=0;
for(int i=1; i<=m; i++)
{
int k;
if( i>r ) k=1;
else k=min( manacher[ind][l+r-i],r-i+1 );
while( i-k>=1&&i+k<=m&&v[ind][i-k]==v[ind][i+k] )
{
k++;
}
manacher[ind][i]=k;
k--;
if( i+k>r )
{
l=i-k;
r=i+k;
}
}
}
void solve(int ind)
{
for(int i=1;i<=n;i++) aux[i]=manacher[i][ind],st[i]=dr[i]=0;
int nr;
for(int i=1;i<=n;i++)
if(i==1) nr=1,stiva[1]=1;
else
{
while( nr&&aux[i]<aux[stiva[nr]] )
{
dr[stiva[nr]]=i;
nr--;
}
stiva[++nr]=i;
}
for(int i=1;i<=nr;i++) dr[stiva[i]]=n+1;
for(int i=n;i>=1;i--)
if(i==n) nr=1,stiva[1]=n;
else
{
while( nr&&aux[i]<aux[stiva[nr]] )
{
st[stiva[nr]]=i;
nr--;
}
stiva[++nr]=i;
}
for(int i=1;i<=n;i++)
{
int latime=dr[i]-st[i]-1;
int lungime=aux[i]*2-1;
ans=max(ans,latime*lungime);
}
}
int main()
{
f>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
f>>v[i][j];
for(int i=1; i<=n; i++)
compute_manacher(i);
for(int i=1;i<=m;i++)
solve(i);
g<<ans;
}