Pagini recente » Cod sursa (job #317411) | Cod sursa (job #80505) | Cod sursa (job #3221399) | Cod sursa (job #2218191) | Cod sursa (job #822228)
Cod sursa(job #822228)
#include<cstdio>
#include<stack>
#include<algorithm>
using std::stack;
using std::max;
struct str
{
int s,h;
str()
{
s=h=0;
}
str (int ss,int hh)
{
s=ss;
h=hh;
}
};
static int v[205][205];
static stack<struct str> st;
static int h[205];
static int mxa,mxb;
static void calcaltpeste (int j1,int j2)
{
mxa=0;
mxb=0;
for(int j=j1;j<j2;j++){
int p=j;
while(st.empty()||st.top().h!=h[j]){
if(st.empty()||st.top().h<h[j])
st.push (str (p,h[j]));
else if(st.top().h>h[j]){
int xx=st.top().h;
int yy=j-st.top().s;
if(yy*xx>mxa*mxb){
mxa=xx;
mxb=yy;
}
p=st.top().s;
st.pop();
}
}
}
while(!st.empty()){
int xx=st.top().h;
int yy=j2-st.top().s;
if(xx*yy>mxa*mxb)
mxa=xx,mxb=yy;
st.pop();
}
}
static int calcpeste (int i1,int j1,int i2,int j2)
{
for(int j=j1;j<j2;j++)
h[j]=!v[i1][j];
int mmxa=0,mmxb=0;
for(int l=i1;l<i2;){
calcaltpeste (j1,j2);
l++;
for(int j=j1;j<j2;j++)
if(v[l][j])
h[j]=0;
else
h[j]++;
if(mxa*mxb>mmxa*mmxb)
mmxa=mxa,mmxb=mxb;
}
return mmxa*mmxb;
}
int main()
{
freopen ("bmatrix.in","r",stdin);
#ifdef INFOARENA
freopen ("bmatrix.out","w",stdout);
#endif
int m,n;
scanf ("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf (" ");
for(int j=0;j<n;j++)
v[i][j]=getchar()-'0';
}
int mx=0;
for(int i=1;i<m;i++){
int c=calcpeste (0,0,i,n)+calcpeste (i,0,m,n);
if(c>mx)
mx=c;
}
for(int i=1;i<n;i++){
int c=calcpeste (0,0,m,i)+calcpeste (0,i,m,n);
if(c>mx)
mx=c;
}
printf ("%d",mx);
return 0;
}