Pagini recente » Cod sursa (job #2040876) | Cod sursa (job #2354864) | Cod sursa (job #2100829) | Cod sursa (job #1232642) | Cod sursa (job #639775)
Cod sursa(job #639775)
#include <stdio.h>
#define NMAX 1005
#define LMAX 20005
#define P 1000007
#define MOD
inline int cif(char x)
{
return x>='0' && x<='9';
}
int n,m,A[NMAX][NMAX],rez,H[NMAX],G[NMAX];
char line[LMAX];
struct stiva{int f,s;};
stiva E[NMAX];
short int B[NMAX][NMAX],C[NMAX][NMAX],D[NMAX][NMAX];
void read()
{
scanf("%d%d\n",&n,&m);
int i,j,poz;
for (i=1; i<=n; i++)
{
fgets(line+1,LMAX,stdin);
poz=0;
for (j=1; j<=m; j++)
{
while (!cif(line[poz+1])) poz++;
while (cif(line[poz+1])) {poz++; A[i][j]=A[i][j]*10+line[poz]-'0';}
}
}
}
inline int max(int x,int y)
{
return x>y ? x : y;
}
inline int min(int x,int y)
{
return x<y ? x : y;
}
void partI()
{
int i,j,a,b,c,st,dr;
for (i=1; i<=n; i++)
{
st=0; dr=0;
for (j=1; j<=m; j++)
{
if (i>dr)
{
a=b=j;
while (A[i][a-1]==A[i][b+1] && a-1>=1 && b+1<=m)
a--,b++;
st=a; dr=b;
H[j]=st; G[j]=dr;
B[i][j]=H[j];
}
else
{
a=st+(dr-j);
b=H[a]; c=G[a];
if (b>st)
{
H[j]=j-(a-b);
G[j]=j+(a-b);
B[i][j]=H[j];
}
else
{
a=j-(dr-j); b=dr;
while (A[i][a-1]==A[i][b+1] && a-1>=1 && b+1<=m)
a--,b++;
st=a; dr=b;
H[j]=a; G[j]=b;
B[i][j]=H[j];
}
}
}
}
}
void partII()
{
int i,j,r,act;
for (j=1; j<=m; j++)
{
r=0;
for (i=1; i<=n; i++)
{
act=i;
while (B[i][j]>=E[r].f && r)
{
act=min(act,E[r].s);
r--;
}
E[++r].f=B[i][j]; E[r].s=act;
C[i][j]=act;
}
r=0;
for (i=n; i>=1; i--)
{
act=i;
while (B[i][j]>=E[r].f && r)
{
act=max(act,E[r].s);
r--;
}
E[++r].f=B[i][j]; E[r].s=act;
D[i][j]=act;
}
for (i=1; i<=n; i++)
rez=max(rez,(D[i][j]-C[i][j]+1)*(2*(j-B[i][j])+1));
}
}
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
read();
partI();
partII();
printf("%d\n",rez);
return 0;
}