Pagini recente » Cod sursa (job #610526) | Cod sursa (job #1746837) | Cod sursa (job #1954811) | Cod sursa (job #1707259) | Cod sursa (job #2374576)
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("dreptpal.in");
ofstream fo("dreptpal.out");
int n,rez,i,A[1005][2005],m,j,k,inv,c,dr,Lp[1005][2005],Pst[1005],pdr,ind;
deque<int> Q;
int main()
{
fi>>n>>m;
for(i=1; i<=n; i++)
{
ind=0;
for(j=1; j<=m; j++)
{
A[i][++ind]=-1;
fi>>A[i][++ind];
}
A[i][++ind]=-1;
}
m=ind;
for(i=1; i<=n; i++)
{
c=0;
dr=0;
for(j=1; j<=m; j++)
{
if(j<=dr)
{
inv=c-(j-c);
if(inv-Lp[i][inv]>c-Lp[i][c])
Lp[i][j]=Lp[i][inv];
else
{
for(k=dr-j+1; k<=min(j-1,m-j); k++)
if(A[i][j+k]!=A[i][j-k])
break;
Lp[i][j]=k;
c=j;
dr=j+k-1;
}
}
else
{
for(k=1; k<=min(j-1,m-j); k++)
if(A[i][j+k]!=A[i][j-k])
break;
Lp[i][j]=k;
c=j;
dr=j+k-1;
}
}
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
Lp[i][j]=Lp[i][j]/2;
for(j=1; j<=m; j++)
{
Q.clear();
for(i=1; i<=n; i++)
{
while(!Q.empty() && Lp[Q.back()][j]>=Lp[i][j])
Q.pop_back();
if(!Q.empty())
Pst[i]=i-Q.back();
else
Pst[i]=i;
Q.push_back(i);
}
Q.clear();
for(i=n; i>=1; i--)
{
while(!Q.empty() && Lp[Q.back()][j]>=Lp[i][j])
Q.pop_back();
if(!Q.empty())
pdr=Q.back()-i-1;
else
pdr=n-i;
Q.push_back(i);
if(A[1][j]==-1)
rez=max(rez,(Pst[i]+pdr)*2*Lp[i][j]);
else
rez=max(rez,(Pst[i]+pdr)*(2*Lp[i][j]-1));
}
}
fo<<rez<<"\n";
fi.close();
fo.close();
return 0;
}