Pagini recente » Cod sursa (job #2701859) | Cod sursa (job #2162436) | Cod sursa (job #1058623) | Cod sursa (job #354726) | Cod sursa (job #1558950)
#include <cstdio>
#define NMAX 223
using namespace std;
int s[NMAX],poz;
int n,m;
int h1[NMAX][NMAX],h2[NMAX][NMAX];
int in[NMAX];
bool apar[NMAX],a[NMAX][NMAX],b[NMAX][NMAX];
int doit(const int &p1,const int &p2)
{
int maxim=0;
for(int i=1;i<=n;i++)
{
for(int j=p1;j<=p2;j++)
{
if((poz==0))
{
apar[h1[i][j]]=1;
s[++poz]=(h1[i][j]);
}
else
{
while(1)
{
if((poz==0)) break;
int nod=s[poz];
if(nod>h1[i][j])
{
if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
if(in[h1[i][j]]==0||in[nod]<in[h1[i][j]]) in[h1[i][j]]=in[nod];
in[nod]=0;
apar[nod]=0;
--poz;;
}
else break;
}
if(apar[h1[i][j]]==0)
{
apar[h1[i][j]]=1;
s[++poz]=(h1[i][j]);
}
}
if(in[h1[i][j]]==0||j<in[h1[i][j]]) in[h1[i][j]]=j;
}
while(!(poz==0))
{
int nod=s[poz];
if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
in[nod]=0;
apar[nod]=0;
--poz;;
}
}
return maxim;
}
int doit2(const int &p1,const int &p2)
{
int maxim=0;
for(int i=1;i<=m;i++)
{
for(int j=p1;j<=p2;j++)
{
if((poz==0))
{
apar[h2[i][j]]=1;
s[++poz]=(h2[i][j]);
}
else
{
while(1)
{
if((poz==0)) break;
int nod=s[poz];
if(nod>h2[i][j])
{
if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
if(in[h2[i][j]]==0||in[nod]<in[h2[i][j]]) in[h2[i][j]]=in[nod];
in[nod]=0;
apar[nod]=0;
--poz;;
}
else break;
}
if(apar[h2[i][j]]==0)
{
apar[h2[i][j]]=1;
s[++poz]=(h2[i][j]);
}
}
if(in[h2[i][j]]==0||j<in[h2[i][j]]) in[h2[i][j]]=j;
}
while(!(poz==0))
{
int nod=s[poz];
if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
in[nod]=0;
apar[nod]=0;
--poz;;
}
}
return maxim;
}
int main()
{
freopen ("bmatrix.in","r",stdin);
freopen ("bmatrix.out","w",stdout);
scanf("%d%d",&n,&m);
char ch;
for(int i=1;i<=n;i++)
{
scanf("%c",&ch);
for(int j=1;j<=m;j++)
{
scanf("%c",&ch);
a[i][j]=(ch-'0');
b[j][i]=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) if(a[i][j]==0) h1[i][j]=h1[i-1][j]+1;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) if(b[i][j]==0) h2[i][j]=h2[i-1][j]+1;
}
int maxim=0;
for(int i=1;i<m;i++)
{
int sum=doit(1,i)+doit(i+1,m);
if(maxim<sum) maxim=sum;
}
for(int i=1;i<n;i++)
{
int sum=doit2(1,i)+doit2(i+1,n);
if(maxim<sum) maxim=sum;
}
printf("%d\n",maxim);
}