Pagini recente » Arhiva de probleme | Cod sursa (job #2005738) | Cod sursa (job #2015212) | Cod sursa (job #721666) | Cod sursa (job #673876)
Cod sursa(job #673876)
#include <cstdio>
#include <stack>
#define NMAX 201
using namespace std;
int aux[NMAX][NMAX], a[NMAX][NMAX], m, n;
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)
{
if(a[i][j] == 0)
{
aux[i][j] = aux[i-1][j] + 1;
}
else
{
aux[i][j] = 0;
}
}
}
int best = 0;
for(int i=y1;i<=y2;++i)
{
stack<pair<int, int> >S;
S.push(make_pair(x1-1,-1));
for(int j=x1;j<=x2;++j)
{
while(aux[i][j] <= S.top().second)
{
S.pop();
}
if(best < aux[i][j] * (j - S.top().first))
{
best = aux[i][j] * (j - S.top().first);
}
S.push(make_pair(j, aux[i][j]));
}
stack<pair<int, int> >S2;
S2.push(make_pair(x2+1,-1));
for(int j=x2;j>=x1;--j)
{
while(aux[i][j] <= S2.top().second)
{
S2.pop();
}
if(best < aux[i][j] * (S2.top().first - j))
{
best = aux[i][j] * (S2.top().first - j);
}
S2.push(make_pair(j, aux[i][j]));
}
}
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", s);
for(int j=1;j<=n;++j)
{
a[i][j] = s[j-1] - '0';
}
}
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;
}
}
printf("%d", best);
return 0;
}