Pagini recente » Cod sursa (job #1484021) | Cod sursa (job #2712663) | Cod sursa (job #238837) | Cod sursa (job #1487529) | Cod sursa (job #1914694)
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;
const int NMAX=205;
stack <int> stiva;
int v[NMAX],st[NMAX],dr[NMAX],up[205][205],up2[205],down2[205];
char mat[205][205],mat2[205][205]; /////////////////!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
char s[205];
int n,m,rez1,rez2;
void dreptunghi()
{
int maxim=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if(mat[i][j]==1)
up[i][j]=0;
else
up[i][j]=up[i-1][j]+1;
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=m; i++)
{
while(!stiva.empty() && up[k][i]<=up[k][stiva.top()])
stiva.pop();
if(stiva.empty())
st[i]=0;
else
st[i]=stiva.top();
stiva.push(i);
}
while(!stiva.empty())
stiva.pop();
for(int i=m; i>=1; i--)
{
while(!stiva.empty() && up[k][i]<=up[k][stiva.top()])
stiva.pop();
if(stiva.empty())
dr[i]=m+1;
else
dr[i]=stiva.top();
stiva.push(i);
}
maxim=0;
for(int i=1; i<=m; i++)
{
if(up[k][i]*(dr[i]-st[i]-1)>maxim)
maxim=up[k][i]*(dr[i]-st[i]-1);
st[i]=dr[i]=0;
}
while(!stiva.empty())
stiva.pop();
down2[k]=max(down2[k-1],maxim);
}
}
void rezultat()
{
dreptunghi();
for(int i=1; i<=n; i++)
up2[i]=down2[i];
for(int i=1; i<=n/2; i++)
for(int j=1; j<=m; j++)
{
swap(mat[i][j],mat[n-i+1][j]);
}
dreptunghi();
reverse(down2+1,down2+n+1);
rez2=0;
for(int i=1; i<n; i++)
rez2=max(rez2,down2[i+1]+up2[i]);
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d%d ",&n,&m);
int nrch,rezmax;
for(int i=1; i<=n; i++)
{
gets(s+1);
for(int j=1; j<=m; j++)
mat[i][j]=s[j]-'0';
}
rezultat();
rez1=rez2;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
mat2[j][n-i+1]=mat[i][j];
swap(n,m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
mat[i][j]=mat2[i][j];
rezultat();
rez1=max(rez1,rez2);
printf("%d",rez1);
return 0;
}