Pagini recente » Cod sursa (job #1124675) | Cod sursa (job #2719769) | Fotbal2 | Cod sursa (job #2407070) | Cod sursa (job #1189133)
#include <cstdio>
#include <algorithm>
#define Nmax 205
using namespace std;
int N,M,dp[Nmax][Nmax],s[Nmax][Nmax];
char a[Nmax][Nmax];
inline int LenMax(int a[], int n)
{
int l=0,i,cnt=0;
for(i=1;i<=n;++i)
if(!a[i])
++l;
else
{
cnt=max(cnt,l);
l=0;
}
cnt=max(cnt,l);
return cnt;
}
inline void Dinamic()
{
int i,j,k,v[Nmax];
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
s[i][j]=s[i-1][j]+a[i][j]-'0';
for(i=N;i;--i)
for(j=i;j<=N;++j)
{
for(k=1;k<=M;++k)
v[k]=s[j][k]-s[i-1][k];
dp[i][j]=LenMax(v,M)*(j-i+1);
if(i<j)
dp[i][j]=max(dp[i][j],dp[i+1][j]);
if(i<j)
dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
}
inline void Rotate()
{
int i,j,aux;
char b[Nmax][Nmax];
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
b[j][N-i+1]=a[i][j];
for(i=1;i<=M;++i)
for(j=1;j<=N;++j)
a[i][j]=b[i][j];
aux=N; N=M; M=aux;
}
int main()
{
int i,sol=0;
freopen ("bmatrix.in","r",stdin);
freopen ("bmatrix.out","w",stdout);
scanf("%d%d", &N,&M);
for(i=1;i<=N;++i)
scanf("%s", (a[i]+1));
Dinamic();
for(i=1;i<=N;++i)
sol=max(sol,dp[1][i]+dp[i+1][N]);
Rotate();
Dinamic();
for(i=1;i<=N;++i)
sol=max(sol,dp[1][i]+dp[i+1][N]);
printf("%d\n", sol);
return 0;
}