Pagini recente » Cod sursa (job #49744) | Cod sursa (job #1321172) | Cod sursa (job #2341845) | Cod sursa (job #460092) | Cod sursa (job #1471849)
#include<stdio.h>
#include<algorithm>
#include<stack>
#define mp make_pair
#define maxn 1005
using namespace std;
int n,m,sol;
int a[maxn][maxn],p[maxn][maxn];
int up[maxn],dw[maxn];
stack< pair<int,int> > s;
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
int expand(int k,int left,int right)
{
int nrc=0;
for(;left && right<=m && a[k][left]==a[k][right];left--,right++)
nrc++;
return nrc;
}
void manacher(int k)
{
int R=0,C;
int img;
for(int i=1;i<=m;i++)
{
if(R>=i){
img=2*C-i;
p[k][i]=min(p[k][img],R-i);
}
p[k][i]+=expand(k,i-p[k][i]-1,i+p[k][i]+1);
if(i+p[k][i]>=R) R=i+p[k][i],C=i;
}
}
void solve()
{
for(int i=1;i<=n;i++)
manacher(i);
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
while(!s.empty() && p[i][j]<s.top().first)
dw[s.top().second]=i,s.pop();
s.push(mp(p[i][j],i));
}
for(;!s.empty();s.pop()) dw[s.top().second]=n+1;
for(int i=n;i;i--)
{
while(!s.empty() && p[i][j]<s.top().first)
up[s.top().second]=i,s.pop();
s.push(mp(p[i][j],i));
}
for(;!s.empty();s.pop()) up[s.top().second]=0;
for(int i=1;i<=n;i++)
sol=max(sol,(p[i][j]*2+1)*(dw[i]-up[i]-1));
}
}
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
read();
solve();
printf("%d",sol);
fclose(stdin);
fclose(stdout);
return 0;
}