Pagini recente » Monitorul de evaluare | Istoria paginii runda/preoji2010_runda1/clasament | Cod sursa (job #1814374) | Cod sursa (job #502654) | Cod sursa (job #1980589)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int nmax=1005;
string str;
int a[nmax][nmax],st[nmax],t[nmax],u,s[2*nmax],p[2*nmax],sir[nmax];
int n,m,i,j,mx,r,c,num,ch;
int getnum()
{
num=0;
while(str[ch]>='0'&&str[ch]<='9')
{
num=num*10+str[ch]-'0';
ch++;
}
ch++;
return num;
}
int main()
{
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
f>>n>>m;
s[0]=-2;
for(i=1;i<=m;i++)
s[2*i-1]=-1;
getline(f,str);
for(i=1;i<=n;i++)
{
getline(f,str);ch=0;
for(j=1;j<=m;j++)
s[2*j]=getnum();
r=0,c=0;
for(j=1;j<=2*m;j++)
p[j]=0;
for(j=1;j<=2*m;j++)
{
if(j<=r)
p[j]=min(p[2*c-j],r-j);
while(j-p[j]>=1&&j+p[j]<=2*m&&s[j-p[j]]==s[j+p[j]])
p[j]++;
if(j+p[j]>r)
r=j+p[j],c=j;
p[j]--;
}
for(j=1;j<=m;j++)
{a[i][j]=2*(p[2*j]/2)+1;}
}
for(j=1;j<=m;j++)
{
for(i=1;i<=n;i++)
sir[i]=a[i][j];
u=0;st[0]=0;
for(i=1;i<=n;i++)
{
while(u>0&&sir[i]<sir[st[u]])
u--;
t[i]=i-st[u];
u++;
st[u]=i;
}
u=0;st[0]=n+1;
for(i=n;i>=1;i--)
{
while(u>0&&sir[i]<=sir[st[u]])
u--;
t[i]+=(st[u]-i-1);
u++;
st[u]=i;
if(t[i]*sir[i]>mx)
mx=t[i]*sir[i];
}
}
g<<mx;
return 0;
}