Pagini recente » Cod sursa (job #1615172) | Cod sursa (job #3232852) | Cod sursa (job #2553354) | Cod sursa (job #443061) | Cod sursa (job #475117)
Cod sursa(job #475117)
#include <cstdio>
#include <cstring>
#define file_in "bmatrix.in"
#define file_out "bmatrix.out"
int n,m;
char a[210][210];
int b[210][210];
int v[210];
void citire()
{
int i;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d\n", &n, &m);
for (i=0;i<n;++i)
fgets(a[i],m+2,stdin);
}
inline int min(int a, int b) { return a<b?a:b; }
inline int max(int a, int b) { return a>b?a:b; }
void solve()
{
int i,j,x,rez,k,h;
//preprocesare
for (i=0;i<n;++i)
{
for (j=0;j<m;++j)
if (a[i][j]=='0')
v[j]++;
else
v[j]=0;
for (j=0;j<m;++j)
{
if (i!=0 && j!=0)
b[i][j]=max(b[i][j],b[i-1][j-1]);
if (i!=0)
b[i][j]=max(b[i][j],b[i-1][j]);
if (j!=0)
b[i][j]=max(b[i][j],b[i][j-1]);
h=v[j];
for (k=j;k>=0;--k)
{
b[i][j]=max(b[i][j],(j-k+1)*h);
if (k!=0)
h=min(h,v[k-1]);
}
}
}
//orizontal
i=0;
while(i<m)
v[i++]=0;
for (i=0;i<n;++i)
{
for (j=0;j<m;++j)
if (a[i][j]=='0')
v[j]++;
else
v[j]=0;
for (j=1;j<m;++j)
{
x=0;
h=v[j];
for (k=j;k<m;++k)
{
x=max(x,(k-j+1)*h);
if (k<m)
h=min(h,v[k+1]);
}
rez=max(rez,x+b[n-1][j-1]);
}
}
//vertical
i=0;
while(i<n)
v[i++]=0;
for (i=0;i<m;++i)
{
for (j=0;j<n;++j)
if (a[j][i]=='0')
v[j]++;
else
v[j]=0;
for (j=1;j<n;++j)
{
x=0;
h=v[j];
for (k=j;k<n;++k)
{
x=max(x,(k-j+1)*h);
if (k<n)
h=min(h,v[k+1]);
}
rez=max(rez,x+b[j-1][m-1]);
}
}
printf("%d\n", rez);
}
int main()
{
citire();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}