Pagini recente » Cod sursa (job #2659790) | Cod sursa (job #1196200) | Cod sursa (job #2660216) | Cod sursa (job #1102963) | Cod sursa (job #1542312)
#include <cstdio>
#include <stack>
#define NMAX 450
using namespace std;
stack<int> s;
int n,m;
int a[NMAX][NMAX],b[NMAX][NMAX],h1[NMAX][NMAX],h2[NMAX][NMAX];
int in[223];
int doit(int p1,int p2)
{
int maxim=0;
for(int i=1;i<=n;i++)
{
for(int j=p1;j<=p2;j++)
{
if(s.empty()) s.push(h1[i][j]);
else
{
while(1)
{
if(s.empty()) break;
int nod=s.top();
if(nod>h1[i][j])
{
if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
in[nod]=0;
while(!s.empty()&&s.top()==nod) s.pop();
}
else break;
}
s.push(h1[i][j]);
}
if(in[h1[i][j]]==0) in[h1[i][j]]=j;
}
while(!s.empty())
{
int nod=s.top();
if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
in[nod]=0;
while(!s.empty()&&s.top()==nod) s.pop();
}
}
return maxim;
}
int doit2(int p1,int p2)
{
int maxim=0;
for(int i=1;i<=m;i++)
{
for(int j=p1;j<=p2;j++)
{
if(s.empty()) s.push(h2[i][j]);
else
{
while(1)
{
if(s.empty()) break;
int nod=s.top();
if(nod>h2[i][j])
{
if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
in[nod]=0;
while(!s.empty()&&s.top()==nod) s.pop();
}
else break;
}
s.push(h2[i][j]);
}
if(in[h2[i][j]]==0) in[h2[i][j]]=j;
}
while(!s.empty())
{
int nod=s.top();
if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
in[nod]=0;
while(!s.empty()&&s.top()==nod) s.pop();
}
}
//printf("%d %d %d\n",p1,p2,maxim);
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]=1-(ch-'0');
b[j][n-i+1]=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) if(a[i][j]==1) h1[i][j]=h1[i-1][j]+1;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) printf("%d",1-b[i][j]);
printf("\n");
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) if(b[i][j]==1) 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);
}