Pagini recente » Cod sursa (job #1647766) | Cod sursa (job #121372) | Cod sursa (job #1288401) | Cod sursa (job #2029044) | Cod sursa (job #2468051)
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
const int NMAX=205;
int st[NMAX],dr[NMAX],mat1[NMAX][NMAX],mat2[NMAX][NMAX],s1[NMAX][NMAX],s2[NMAX][NMAX],dp1[NMAX],dp2[NMAX];
int n,m;
stack<pair<int, int>> aux;
int formare(int v[NMAX]){
///formam vectorul st
while(!aux.empty())
aux.pop();
st[1]=0;
aux.push(make_pair(v[1], 1));
for(int i=2;i<=m;i++){
while(!aux.empty() && aux.top().first>=v[i])
aux.pop();
if(v[i]==v[i-1])
st[i]=st[i-1]+1;
else
if(v[i]>v[i-1])
st[i]=0;
else
if(aux.empty())
st[i]=i-1;
else
st[i]=i-aux.top().second-1;
aux.push(make_pair(v[i], i));
}
while(!aux.empty())
aux.pop();
///formam vectorul dr
dr[m]=0;
aux.push(make_pair(v[m], m));
for(int i=m-1;i>0;i--){
while(!aux.empty() && aux.top().first>=v[i])
aux.pop();
if(v[i]==v[i+1])
dr[i]=dr[i+1]+1;
else
if(v[i]>v[i+1])
dr[i]=0;
else{
if(aux.empty())
dr[i]=m-i;
else
dr[i]=aux.top().second-i-1;
}
aux.push(make_pair(v[i], i));
}
int sum=0;
for(int i=1;i<=m;i++)
sum=max(sum, v[i]*(st[i]+dr[i]+1));
return sum;
}
int rezolvare(int d[NMAX][NMAX]){
for(int i=1;i<=n;i++)
dp1[i]=dp2[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(d[i][j]==0)
s1[i][j]=1+s1[i-1][j];
else
s1[i][j]=0;
for(int i=n;i>=1;i--)
for(int j=1;j<=m;j++)
if(d[i][j]==0)
s2[i][j]=1+s2[i+1][j];
else
s2[i][j]=0;
for(int i=1;i<=n;i++){
int x=formare(s1[i]);
dp1[i]=max(dp1[i-1], x);
}
for(int i=n;i>=1;i--){
int x=formare(s2[i]);
dp2[i]=max(dp2[i+1], x);
}
int sol=0;
for(int i=1;i<n;i++)
sol=max(sol, dp1[i]+dp2[i+1]);
return sol;
}
int main(){
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d%d ", &n, &m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char ch;
scanf("%c ", &ch);
mat1[i][j]=ch-'0';
mat2[j][i]=ch-'0';
}
int x1=rezolvare(mat1);
swap(n, m);
int x2=rezolvare(mat2);
printf("%d", max(x1, x2));
return 0;
}