Pagini recente » Cod sursa (job #607426) | Cod sursa (job #2574400) | Cod sursa (job #1210935) | Cod sursa (job #3157476) | Cod sursa (job #991042)
Cod sursa(job #991042)
#include<fstream>
#define N 209
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int vf,n,m,i,j,sol,st[N],a[N][N],r[N][N],l[N][N];
char s[N];
inline int rez1(int p1,int p2)
{
int i,j,sol=0;
for(i=p1;i<=p2;++i)
for(j=1;j<=m;++j)
{
sol=max(sol,(r[i][j]-l[i][j]-1)*min(a[i][j],i-p1+1));
}
return sol;
}
inline int rez2(int p1,int p2)
{
int i,j,sol=0;
for(i=1;i<=n;++i)
for(j=p1;j<=p2;++j)
{
sol=max(sol,(min(r[i][j],p2+1)-max(l[i][j],p1-1)-1)*a[i][j]);
}
return sol;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
{
f>>(s+1);
for(j=1;j<=m;++j)
{
if(s[j]=='0')
a[i][j]=a[i-1][j]+1;
}
}
for(i=1;i<=n;++i)
{
st[0]=0;
vf=0;
for(j=1;j<=m;++j)
{
while(vf&&a[i][st[vf]]>=a[i][j])
--vf;
l[i][j]=st[vf];
st[++vf]=j;
}
st[0]=m+1;
vf=0;
for(j=m;j;--j)
{
while(vf&&a[i][st[vf]]>=a[i][j])
--vf;
r[i][j]=st[vf];
st[++vf]=j;
}
}
for(i=2;i<=n;++i)
{
sol=max(sol,rez1(1,i-1)+rez1(i,n));
}
for(j=2;j<=m;++j)
{
sol=max(sol,rez2(1,j-1)+rez2(j,m));
}
g<<sol<<'\n';
return 0;
}