Pagini recente » Cod sursa (job #407832) | Cod sursa (job #637574) | Cod sursa (job #2085133) | Cod sursa (job #2365056) | Cod sursa (job #1386789)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 210
using namespace std;
int n , m , i , j , k , Max[3] , Lf[3] , Ls[3] , Cf[3] , Cs[3];
int A[Nmax][Nmax] , H[Nmax] , l[Nmax] , q[Nmax];
char s[Nmax];
void dreptunghi()
{
int kk , nn , cnt;
for (cnt = 1; cnt <= 2; ++cnt)
{
//memset(H , 0 , sizeof(H));
for (Max[cnt] = 0 , kk = Lf[cnt]; kk <= Ls[cnt]; ++kk)
{
for (j = Cf[cnt]; j <= Cs[cnt]; ++j)
if (kk == Lf[cnt]) H[j] = (A[kk][j] == 1) ? 1 : 0;
else H[j] = (A[kk][j] == 1) ? H[j] + 1 : 0;
//memset(l , 0 , sizeof(l));
//for (j = Cf[cnt] - 1; j <= Cs[cnt] + 1; ++j) l[j] = 0;
H[Cf[cnt]-1] = -1; q[Cf[cnt]-1] = nn = Cf[cnt]-1;
for (i = Cf[cnt]; i <= Cs[cnt]; ++i)
{
j = nn;
while (H[q[j]] >= H[i]) --j;
nn = ++j; l[i] = i - q[j-1]; q[j]=i;
}
H[Cs[cnt]+1] = -1; q[Cf[cnt]-1] = Cs[cnt] + 1; nn = Cf[cnt]-1;
for (i = Cs[cnt]; i > Cf[cnt] - 1; --i)
{
j = nn;
while (H[q[j]] >= H[i]) --j;
nn = ++j; l[i] += q[j-1] - i - 1; q[j] = i;
Max[cnt] = max(Max[cnt] , l[i] * H[i]);
}
}
}
Max[0] = max(Max[0] , Max[1] + Max[2]);
}
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(s+1);
for (j = 1; j <= m; ++j)
A[i][j] = (s[j] == '0');
}
for (k = 1; k <= n; ++k)
{
/// prima matrice (1,1) - (k,m)
/// a doua matrice (k+1,1) - (n,m)
Lf[1] = 1; Ls[1] = k; Cf[1] = 1; Cs[1] = m;
Lf[2] = k + 1; Ls[2] = n; Cf[2] = 1; Cs[2] = m;
dreptunghi();
}
for (k = 1; k <= m; ++k)
{
/// prima matrice (1,1) - (n,k)
/// a doua matrice (1,k+1) - (n,m)
Lf[1] = 1; Ls[1] = n; Cf[1] = 1; Cs[1] = k;
Lf[2] = 1; Ls[2] = n; Cf[2] = k + 1; Cs[2] = m;
dreptunghi();
}
printf("%d\n", Max[0]);
return 0;
}