Pagini recente » Cod sursa (job #1699815) | Cod sursa (job #2372780) | Cod sursa (job #2742073) | Cod sursa (job #2347485) | Cod sursa (job #1841935)
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[255][255];
void rot(int &n,int &m)
{
int i,j,aux[255][255];
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
aux[j][n-i+1]=a[i][j];
swap(n,m);
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
a[i][j]=aux[i][j];
}
int up[255],down[255],c[255][255],l[255],r[255],st[255];
int soldiers_row(int a[255],int n)
{
int i,k;
k=0;
st[0]=0;
for(i=1; i<=n; i++)
{
while(k>0 && a[st[k]]>=a[i]) k--;
l[i]=st[k];
st[++k]=i;
}
k=0;
st[0]=n+1;
for(i=n; i>=1; i--)
{
while(k>0 && a[st[k]]>=a[i]) k--;
r[i]=st[k];
st[++k]=i;
}
int ans=0;
for(i=1; i<=n; i++)
ans=max(ans,a[i]*(r[i]-l[i]-1));
return ans;
}
void get_up(int n,int m,int up[250])
{
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if(a[i][j]==1) c[i][j]=0;
else c[i][j]=c[i-1][j]+1;
}
for(i=1; i<=n; i++)
up[i]=max(up[i-1],soldiers_row(c[i],m));
}
int solve(int n,int m)
{
int i;
get_up(n,m,up);
rot(n,m);
rot(n,m);
get_up(n,m,down);
reverse(down+1,down+n+1);
int ans=0;
for(i=1; i<n; i++)
ans=max(ans,up[i]+down[i+1]);
return ans;
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
int i,j;
char s[255];
scanf("%d%d\n",&n,&m);
for(i=1; i<=n; i++)
{
gets(s);
for(j=1; j<=m; j++)
a[i][j]=s[j-1]-'0';
}
int ans;
ans=solve(n,m);
rot(n,m);
ans=max(ans,solve(n,m));
printf("%d\n",ans);
return 0;
}