Pagini recente » Cod sursa (job #1318442) | Cod sursa (job #1200075) | Cod sursa (job #2178343) | Cod sursa (job #1497598) | Cod sursa (job #1393619)
#include <cstdio>
#include <cstring>
FILE* in=fopen("bmatrix.in","r");
FILE* out=fopen("bmatrix.out","w");
const int Q=205;
char v[Q][Q];
int aux[Q][Q];
int r[5][Q];
int up[Q][Q];
int st[Q],dr[Q];
int stv[Q],nr;
void cerere(int v[Q][Q], int l, int c, int rez[Q])
{
memset(up,0,sizeof up);
for(int j=1; j<=c; j++)
{
for(int i=1; i<=l; i++)
{
if(v[i][j]==0)
up[i][j]=up[i-1][j]+1;
}
}
for(int i=1; i<=l; i++)
{
for(int j=1; j<=c; j++)
{
while(nr && up[i][stv[nr]] > up[i][j])
{
dr[stv[nr]]=j-1;
nr--;
}
if(v[i][j]==0)
stv[++nr]=j;
}
while(nr)
{
dr[stv[nr]]=c;
nr--;
}
for(int j=c; j>0; j--)
{
while(nr && up[i][stv[nr]] > up[i][j])
{
st[stv[nr]]=j+1;
nr--;
}
if(v[i][j]==0)
stv[++nr]=j;
}
while(nr)
{
st[stv[nr]]=1;
nr--;
}
for(int j=1; j<=c; j++)
{
if(v[i][j]==1)
continue;
if((dr[j]-st[j]+1)*up[i][j] > rez[i])
rez[i]=(dr[j]-st[j]+1)*up[i][j];
}
}
int max=0;
for(int i=1; i<=l; i++)
{
if(max<rez[i])
max=rez[i];
rez[i]=max;
}
}
int main()
{
int l,c;
fscanf(in,"%d%d\n",&l,&c);
for(int i=1; i<=l; i++)
{
fgets(v[i]+1,Q,in);
}
for(int i=1; i<=l; i++)
{
for(int j=1; j<=c; j++)
{
aux[i][j]=v[i][j]-'0';
}
}
cerere(aux,l,c,r[1]);
for(int i=l; i>0; i--)
{
for(int j=1; j<=c; j++)
{
aux[i][j]=v[l-i+1][j]-'0';
}
}
cerere(aux,l,c,r[2]);
int answer=0;
for(int i=1; i<l; i++)
{
if(r[1][i]+r[2][l-i] >answer)
answer=r[1][i]+r[2][l-i];
}
for(int i=1; i<=l; i++)
{
for(int j=1; j<=c; j++)
{
aux[j][i]=v[i][j]-'0';
}
}
cerere(aux,c,l,r[3]);
for(int i=1; i<=l; i++)
{
for(int j=1; j<=c; j++)
{
aux[c-j+1][i]=v[i][j]-'0';
}
}
cerere(aux,c,l,r[4]);
for(int i=1; i<c; i++)
{
if(r[3][i]+r[4][c-i] >answer)
answer=r[3][i]+r[4][c-i];
}
fprintf(out,"%d",answer);
return 0;
}