Pagini recente » Cod sursa (job #2818317) | Cod sursa (job #2418938) | Cod sursa (job #2865958) | Cod sursa (job #2190891) | Cod sursa (job #1729717)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,i,j,st[205],dr[205],a[205][205],q,mx1,mx2,k,s,b[205],MX,qe;
bool v[205][205];
char x;
stack <int>S;
int main()
{fin>>n>>m;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
{fin>>x;
v[i][j]=x-48;
if(v[i][j]==0)a[i][j]=a[i-1][j]+1;
else a[i][j]=0;
}
}
st[0]=0;
dr[0]=m+1;
for(k=1;k<=n-1;k++)
{mx1=0;mx2=0;
for(i=1;i<=k;i++)
{S.push(0);
for(j=1;j<=m;j++)
{st[j]=1;dr[j]=m;
if(S.size()==0)S.push(j);
else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
}
if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
else st[j]=S.top()+1;
S.push(j);
}
}
while(S.size()>0)S.pop();
for(j=1;j<=m;j++)
{s=a[i][j]*(dr[j]-st[j]+1);
// fout<<s<<" ";
if(s>mx1)mx1=s;
}
// fout<<"\n";
}
for(i=k+1;i<=n;i++)
{S.push(0);
for(j=1;j<=m;j++)
b[j]=a[i][j];
for(j=1;j<=m;j++)
{st[j]=1;dr[j]=m;
if(a[i][j]>i-k)a[i][j]=i-k;
if(S.size()==0)S.push(j);
else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
}
if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
else st[j]=S.top()+1;
S.push(j);
}
}
while(S.size()>0)S.pop();
for(j=1;j<=m;j++)
{s=a[i][j]*(dr[j]-st[j]+1);
if(s>mx2)mx2=s;
}
for(j=1;j<=m;j++)
a[i][j]=b[j];
}
if(mx1+mx2>MX&&mx1>0&&mx2>0)MX=mx1+mx2;
}
for(k=1;k<=m-1;k++)
{mx1=0;mx2=0;
for(i=1;i<=n;i++)
{S.push(0);
for(j=1;j<=k;j++)
{st[j]=1;dr[j]=k;
if(S.size()==0)S.push(j);
else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
}
if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
else st[j]=S.top()+1;
S.push(j);
}
}
while(S.size()>0)S.pop();
for(j=1;j<=k;j++)
{s=a[i][j]*(dr[j]-st[j]+1);
// fout<<s<<" ";
if(s>mx1)mx1=s;
}
}
for(i=1;i<=n;i++)
{S.push(k);
qe=a[i][k];
a[i][k]=0;
for(j=k+1;j<=m;j++)
{st[j]=k+1;dr[j]=n;
if(S.size()==0)S.push(j);
else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
}
if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
else st[j]=S.top()+1;
S.push(j);
}
}
while(S.size()>0)S.pop();
for(j=k+1;j<=m;j++)
{s=a[i][j]*(dr[j]-st[j]+1);
// fout<<s<<"* ";
if(s>mx2)mx2=s;
}
a[i][k]=qe;
}
//fout<<"\n";
if(mx1+mx2>MX&&mx1>0&&mx2>0)MX=mx1+mx2;
}
fout<<MX;
}