Pagini recente » Cod sursa (job #64570) | Cod sursa (job #1644308) | Cod sursa (job #1634634) | Cod sursa (job #959336) | Cod sursa (job #878663)
Cod sursa(job #878663)
#include<fstream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,sol;
char A[2][210][210];
int sus[210][210],jos[210][210],solsus[210],soljos[210];
int St[210],vf=-1,st[210],dr[210];
inline int Solve(int p,int n,int m)
{
int i,j,rez=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(A[p][i][j]=='0')
sus[i][j]=sus[i-1][j]+1;
else
sus[i][j]=0;
}
}
for(i=n;i>0;i--)
{
for(j=m;j>0;j--)
{
if(A[p][i][j]=='0')
jos[i][j]=jos[i+1][j]+1;
else
jos[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
solsus[i]=soljos[i]=0;
for(j=1;j<=m;j++)
{
while(vf>=0 && sus[i][St[vf]]>=sus[i][j])
{
dr[St[vf]]=j-1;
vf--;
}
if(vf>=0)
st[j]=St[vf]+1;
else
st[j]=1;
St[++vf]=j;
}
while(vf>=0)
{
dr[St[vf]]=m;
vf--;
}
for(j=1;j<=m;j++)
solsus[i]=max(max(solsus[i-1],solsus[i]),sus[i][j]*(dr[j]-st[j]+1));
//
for(j=1;j<=m;j++)
{
while(vf>=0 && jos[i][St[vf]]>=jos[i][j])
{
dr[St[vf]]=j-1;
vf--;
}
if(vf>=0)
st[j]=St[vf]+1;
else
st[j]=1;
St[++vf]=j;
}
while(vf>=0)
{
dr[St[vf]]=m;
vf--;
}
for(j=1;j<=m;j++)
soljos[i]=max(soljos[i],jos[i][j]*(dr[j]-st[j]+1));
}
for(i=1;i<n;i++)
rez=max(rez,solsus[i]+soljos[i+1]);
return rez;
}
int main()
{
int i,j;
ifstream fin("bmatrix.in");
fin>>n>>m;
for(i=1;i<=n;i++)
fin>>(A[0][i]+1);
fin.close();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
A[1][j][i]=A[0][i][j];
sol=max(Solve(0,n,m),Solve(1,m,n));
ofstream fout("bmatrix.out");
fout<<sol<<"\n";
fout.close();
return 0;
}