Pagini recente » Cod sursa (job #255552) | Cod sursa (job #2176376) | Cod sursa (job #1854524) | Cod sursa (job #1534857) | Cod sursa (job #1171672)
#include <fstream>
#include <algorithm>
using namespace std;
#define NMax 1005
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m;
int M[NMax][NMax];
int P[NMax][NMax];
pair< int,int > v[NMax];
pair< int,int > per[NMax];
int val[NMax];
int valf[NMax];
#define crt v[i].second
int solve(int j)
{
int i;
for(i=1;i<=n;i++)
{
v[i].first=P[i][j];
v[i].second=i;
val[i]=0;
}
sort(v+1,v+n+1);
for(i=n;i>=1;i--)
{
if(!val[crt-1] && !val[crt+1]) per[crt].first=per[crt].second=crt, val[crt]=valf[crt]=1;
else if(val[crt-1] && val[crt+1])
{
per[per[crt-1].first].second=per[crt+1].second;
per[per[crt+1].second].first=per[crt-1].first;
valf[crt]=val[crt]=val[crt-1]+val[crt+1];
val[per[crt-1].first]=val[crt];
val[per[crt+1].second]=val[crt];
}
else if(val[crt-1])
{
per[per[crt-1].first].second=crt;
per[crt].first=per[crt-1].first;
valf[crt]=val[crt]=1+val[crt-1];
val[per[crt-1].first]=val[crt];
}
else
{
per[per[crt+1].second].first=crt;
per[crt].second=per[crt+1].second;
valf[crt]=val[crt]=1+val[crt+1];
val[per[crt+1].second]=val[crt];
}
}
int mx=0;
for(i=1;i<=n;i++)
{
valf[i]*=P[i][j];
if(mx<valf[i]) mx=valf[i];
}
return mx;
}
int main()
{
int i,j;
int L,R,C,p,d;
f>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) f>>M[i][j];
M[i][0]=-1;
C=L=R=0;
for(j=1;j<=m;j++)
{
if(j>R)
{
p=1;
while(M[i][j-p]==M[i][j+p]) p++;
p--;
P[i][j]=(p<<1)|1;
L=j-p,R=j+p,C=j;
}
else
{
d=j-C;
if(C-d-P[i][C-d]/2<L) p=C-d-L+1;
else p=P[i][C-d]/2+1;
while(M[i][j-p]==M[i][j+p]) p++;
p--;
P[i][j]=(p<<1)|1;
if(j+P[i][j]/2>R) L=j-p,R=j+p,C=j;
}
}
}
int mx=0,nr;
for(i=1;i<=m;i++)
{
nr=solve(i);
if(nr>mx) mx=nr;
}
g<<mx<<"\n";
f.close();
g.close();
return 0;
}