Pagini recente » Cod sursa (job #1990981) | Cod sursa (job #785732) | Cod sursa (job #3256725) | Cod sursa (job #460907) | Cod sursa (job #692555)
Cod sursa(job #692555)
#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], b[NMAX][NMAX];
int best[NMAX][4];
int best_dr(int l) //cel mai mare dreptunghi cu baza de jos pe linia l
{
v[0].elm = -1;
v[0].poz = 0;
int top = 0, best = 0;
for(int j=1;j<=n;++j)
{
while(aux[l][j] <= v[top].elm)
{
--top;
}
if(best < aux[l][j] * (j - v[top].poz))
{
best = aux[l][j] * (j - v[top].poz);
}
top++;
v[top].elm = aux[l][j];
v[top].poz = j;
}
return best;
}
void rotate90()
{
for(int j=1;j<=m;++j)
{
for(int i=1;i<=n;++i)
{
b[i][j] = a[m-j+1][i];
}
}
swap(n,m);
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
a[i][j] = b[i][j];
}
}
}
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);
}
for(int j=0;j<4;++j)
{
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
aux[i][j] = a[i][j] == '0' ? aux[i-1][j] + 1 : 0;
}
best[i][j] = max(best_dr(i), best[i-1][j]);
}
if(j<3)
{
rotate90();
}
}
int max = -1;
for(int j=1;j<=m;++j)
{
if(max < best[j][0] + best[n-j][2])
{
max = best[j][0] + best[n-j][2];
}
}
for(int j=1;j<=m;++j)
{
if(max < best[j][1] + best[m-j][3])
{
max = best[j][1] + best[m-j][3];
}
}
printf("%d", max);
return 0;
}