Pagini recente » Cod sursa (job #1246196) | Cod sursa (job #2077798) | Cod sursa (job #873040) | Cod sursa (job #2221644) | Cod sursa (job #1387930)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 210
using namespace std;
int n , m , i , j , k , Max[Nmax][3] , Lf[3] , Ls[3] , Cf[3] , Cs[3] , sol;
int H[Nmax][3] , l[Nmax] , q[Nmax];
char A[Nmax][Nmax];
void dreptunghi()
{
int kk , nn , cnt , start , finish;
for (cnt = 1; cnt <= 2; ++cnt)
{
int t = 0;
for (i = Lf[cnt]; i <= Ls[cnt]; ++i)
for (j = Cf[cnt]; j <= Cs[cnt]; ++j)
H[++t][cnt] = (A[i][j] == '0') ? H[t][cnt] + 1 : 0;
if (Lf[cnt] == Ls[cnt]) start = Cf[cnt] , finish = Cs[cnt];
else start = Lf[cnt] , finish = Ls[cnt];
H[start-1][cnt] = -1; q[start-1] = nn = start-1;
for (i = start; i <= finish; ++i)
{
for (j = nn; H[q[j]][cnt] >= H[i][cnt]; --j);
nn = ++j; l[i] = i - q[j-1]; q[j]=i;
}
H[finish+1][cnt] = -1; q[start-1] = finish + 1; nn = start-1;
for (i = finish; i >= start; --i)
{
for (j = nn; H[q[j]][cnt] >= H[i][cnt]; --j);
nn = ++j; l[i] += q[j-1] - i - 1; q[j] = i;
Max[k][cnt] = max(Max[k][cnt] , l[i] * H[i][cnt]);
}
}
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d %d\n", &n, &m);
for (i = 1; i <= n; ++i)
gets(A[i]+1);
for (k = 1; k <= n; ++k)
{
/// prima matrice (1,1) - (k,m)
/// a doua matrice (n,m) - (n-k+1,1)
Cf[1] = 1; Cs[1] = m; Lf[1] = k; Ls[1] = k;
Cf[2] = 1; Cs[2] = m; Lf[2] = n - k + 1; Ls[2] = n - k + 1;
dreptunghi();
int y = 0;
}
for (i = 1; i <= n; ++i)
sol = max(sol , Max[i][1] + Max[n-i][2]),
Max[i][1] = Max[n-i][2] = 0;
for (j = 1; j <= m; ++j)
H[j][1] = H[j][2] = 0;
for (k = 1; k <= m; ++k)
{
/// prima matrice (1,1) - (n,k)
/// a doua matrice (n,m) - (1,m-k+1)
Lf[1] = 1; Ls[1] = n; Cf[1] = k; Cs[1] = k;
Lf[2] = 1; Ls[2] = n;Cf[2] = m - k + 1; Cs[2] = m - k + 1;
dreptunghi();
}
for (i = 1; i <= m; ++i)
sol = max(sol , Max[i][1] + Max[m-i][2]);
printf("%d\n", sol);
return 0;
}