Pagini recente » Cod sursa (job #879143) | Cod sursa (job #1099628) | Cod sursa (job #1047702) | Cod sursa (job #1779307) | Cod sursa (job #677354)
Cod sursa(job #677354)
#include <cstdio>
#include <algorithm>
#define NMAX 210
using namespace std;
struct elem {
int poz, elm;
} v[NMAX];
int aux[NMAX][NMAX], m, n;
char a[NMAX][NMAX];
int best_dr(int x1, int y1, int x2, int y2) //stanga sus, dreapta jos
{
for(int i=x1;i<=x2;++i)
{
aux[y1-1][i] = 0;
}
for(int i=y1;i<=y2;++i)
{
for(int j=x1;j<=x2;++j)
{
aux[i][j] = a[i][j] == '0' ? aux[i-1][j] + 1 : 0;
}
}
int best = 0;
for(int i=y1;i<=y2;++i)
{
v[0].elm = -1;
v[0].poz = x1 - 1;
int top = 0;
for(int j=x1;j<=x2;++j)
{
while(aux[i][j] <= v[top].elm)
{
--top;
}
if(best < aux[i][j] * (j - v[top].poz))
{
best = aux[i][j] * (j - v[top].poz);
}
top++;
v[top].elm = aux[i][j];
v[top].poz = j;
}
}
return best;
}
void reverse()
{
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n>>1;++j)
{
swap(a[i][j], a[i][n-j+1]);
}
}
}
int solve()
{
int best = 0, b, b1, b2;
for(int i=1;i<n;++i)
{
b1 = best_dr(1,1,i,m);
b2 = best_dr(i+1,1,n,m);
if(b1 && b2)
{
b = b1 + b2;
if(b > best)
best = b;
}
}
for(int i=1;i<m;++i)
{
b1 = best_dr(1,1,n,i);
b2 = best_dr(1,i+1,n,m);
if(b1 && b2)
{
b = b1 + b2;
if(b > best)
best = b;
}
}
return best;
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%d %d", &m, &n);
for(int i=1;i<=m;++i)
{
char s[NMAX];
scanf("%s", a[i]+1);
}
int best1 = solve();
reverse();
int best2 = solve();
if(best1 > best2)
{
printf("%d\n", best1);
return 0;
}
printf("%d\n", best2);
return 0;
}