Pagini recente » Cod sursa (job #226808) | Cod sursa (job #812702) | Cod sursa (job #704655) | Rating Dumitra Andrei 322CC (dumandga) | Cod sursa (job #1256448)
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
bool a[1005][1005];
int s[1005][1005];
int d[1005][1005];
int dir[4][1005];
int n, m;
void process(int k, int n, int m)
{
memset(d, 0, sizeof(d));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j])d[i][j]=0;
else d[i][j]=d[i-1][j]+1;
stack <int> st;
int lf[1005], rg[1005];
memset(lf, 0, sizeof(lf));
memset(rg, 0, sizeof(rg));
for(int i=0;i<n;i++)
{
while(!st.empty())st.pop();
for(int j=0;j<m;j++)
{
while(!st.empty() && d[i][st.top()]>=d[i][j])
st.pop();
if(!st.empty())lf[j]=st.top()+1;
else lf[j]=0;
st.push(j);
}
while(!st.empty())st.pop();
for(int j=m-1;j>=0;j--)
{
while(!st.empty() && d[i][st.top()]>=d[i][j])
st.pop();
if(!st.empty())rg[j]=st.top()-1;
else rg[j]=m-1;
st.push(j);
}
int A=-1;
for(int j=0;j<m;j++)
A=max(A, d[i][j] * (rg[j]-lf[j]+1));
dir[k][i]=max(dir[k][i-1], A);
}
}
bool b[1005][1005];
void rotation()
{
memset(b, 0, sizeof(b));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
b[m-1-j][i]=a[i][j];
int aux=n;
n=m;
m=aux;
memcpy(a, b, sizeof(b));
}
int main()
{
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
{
scanf("\n");
for(int j=0;j<m;j++)
{
char c;
scanf("%c", &c);
a[i][j]=c=='1';
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
for(int k=0;k<4;k++)
{
process(k, n, m);
rotation();
}
reverse(dir[1], dir[1]+m);
reverse(dir[2], dir[2]+n);
int ans=-1;
for(int i=0;i<=n;i++)
ans=max(ans, dir[0][i]+dir[2][i+1]);
for(int i=0;i<=m;i++)
ans=max(ans, dir[3][i]+dir[1][i+1]);
printf("%d\n", ans);
return 0;
}