Pagini recente » Cod sursa (job #1613037) | Cod sursa (job #2004393) | Cod sursa (job #222666) | Cod sursa (job #190750) | Cod sursa (job #636715)
Cod sursa(job #636715)
#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;
int n,m,sol,st1[1002],st2[1002],li[1002],ri[1002],p[1011][2020],a[1001][1001];
void read()
{
assert(freopen("dreptpal.in","r",stdin)!=NULL);
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&a[i][j]);
for(i=1;i<=n;++i)
a[i][0]=2000000000;
}
void do_smen()
{
int i,j,l,k,t;
l=2*m-1;
for(i=1;i<=n;++i)
{
t=0;
k=0;
for(j=1;j<=l;++j)
{
if(t<k)
{
p[i][j]=p[i][j-2*t];
++t;
}
else
{
if(j%2==0)
{
for(k=1;a[i][(j+1)/2+k]==a[i][(j+1)/2-k];++k);
k--;
p[i][j]=k*2;
k=k*2;
t=1;
}
else
{
for(k=0;a[i][(j+1)/2+k]==a[i][(j+1)/2-k];++k);
k--;
p[i][j]=k*2+1;
k=k*2;
t=1;
}
}
printf("%d ",p[i][j]);
}
printf("\n");
}
}
void solve()
{
do_smen();
int i,j;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
while(st1[0] && p[st1[st1[0]]][2*i-1]>p[j][2*i-1])
{
st1[st1[0]]=0;
--st1[0];
}
li[j]=j-st1[st1[0]]-1;
st1[++st1[0]]=j;
}
for(j=n;j>0;--j)
{
while(st2[0] && p[st2[st2[0]]][2*i-1]>p[j][2*i-1])
{
st2[st2[0]]=0;
--st2[0];
}
if(st2[0]==0)
ri[j]=n-j;
else
ri[j]=st2[st2[0]]-j;
st2[++st2[0]]=j;
}
for(j=1;j<=n;++j)
sol=max(sol,p[j][2*i-1]*(ri[j]+li[j]));
while(st2[0])
{
st2[st2[0]]=0;
--st2[0];
}
while(st1[0])
{
st1[st1[0]]=0;
--st1[0];
}
}
}
void write()
{
//assert(freopen("dreptpal.out","w",stdout)!=NULL);
printf("%d",sol);
}
int main()
{
assert(freopen("dreptpal.out","w",stdout)!=NULL);
read();
solve();
write();
return 0;
}