Pagini recente » Cod sursa (job #2676547) | Cod sursa (job #1233186) | Cod sursa (job #1457983) | Borderou de evaluare (job #486995) | Cod sursa (job #1026500)
#include <algorithm>
#include <cstdio>
#include <stack>
#define N 202
#define INF 0x3f3f3f3f
using namespace std;
char a[2][N][N];
int dp[2][N][N], st[N], dr[N], sol[2][N];
int solve(int l, int n, int m)
{
int i, j, ret=0;
stack <int> s;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[l][i][j]=='0') dp[0][i][j]=dp[0][i-1][j]+1;
else dp[0][i][j]=0;
}
}
for(i=n;i;i--)
{
for(j=m;j;j--)
{
if(a[l][i][j]=='0') dp[1][i][j]=dp[1][i+1][j]+1;
else dp[1][i][j]=0;
}
}
for(i=1;i<=n;i++)
{
//sus
sol[0][i]=sol[0][i-1];
for(j=1;j<=m;j++)
{
while(!s.empty()&&dp[0][i][s.top()]>=dp[0][i][j])
{
dr[s.top()]=j-1;
s.pop();
}
if(!s.empty()) st[j]=s.top()+1;
else st[j]=1;
s.push(j);
}
while(!s.empty())
{
dr[s.top()]=m;
s.pop();
}
for(j=1;j<=m;j++) sol[0][i]=max(sol[0][i], dp[0][i][j]*(dr[j]-st[j]+1));
//jos
sol[1][i]=0;
for(j=1;j<=m;j++)
{
while(!s.empty()&&dp[1][i][s.top()]>=dp[1][i][j])
{
dr[s.top()]=j-1;
s.pop();
}
if(!s.empty()) st[j]=s.top()+1;
else st[j]=1;
s.push(j);
}
while(!s.empty())
{
dr[s.top()]=m;
s.pop();
}
for(j=1;j<=m;j++) sol[1][i]=max(sol[1][i], dp[1][i][j]*(dr[j]-st[j]+1));
ret=max(ret, sol[0][i-1]+sol[1][i]);
}
return ret;
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int n, m, i, j;
scanf("%d %d\n", &n, &m);
for(i=1;i<=n;i++)
{
fgets(a[0][i]+1, N+3, stdin);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[1][j][i]=a[0][i][j];
}
}
printf("%d\n", max(solve(0, n, m), solve(1, m, n)));
//printf("%d %d", solve(0, n, m), solve(1, m, n));
}