Pagini recente » Cod sursa (job #2040343) | Cod sursa (job #1539085) | Cod sursa (job #2277331) | Cod sursa (job #190940) | Cod sursa (job #777721)
Cod sursa(job #777721)
# include <fstream>
# include <iostream>
# include <cassert>
# define DIM 202
using namespace std;
int n, m, a[DIM][DIM], b[DIM][DIM], c[DIM][DIM], s[DIM], sol;
void read ()
{
ifstream fin ("bmatrix.in");
fin>>n>>m;
char c;
for(int i=1;i<=n;++i)
{
fin.get();
for(int j=1;j<=m;++j)
{
fin.get(c);
a[i][j] = c-'0';
assert(a[i][j]>=0 && a[i][j]<=1);
b[j][i]=a[i][j];
}
}
}
void solve (int a[DIM][DIM], int n, int m)
{
int st[DIM], d=0;
st[0]=0;
for(int i=0;i<=n+1;++i)
{
for(int j=0;j<=m+1;++j)
c[i][j]=0;
s[i]=0;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
if (!a[i][j])
c[i][j]=c[i-1][j]+1;
else
c[i][j]=0;
c[i][m+1]=0;
}
for(int i=1;i<=n;++i)
{
d=0;
for(int j=1;j<=m+1;++j)
{
while(d && c[i][st[d]]>=c[i][j])
{
s[i]=max(s[i],c[i][st[d]]*(st[d]-st[d-1]));
--d;
}
st[++d]=j;
}
s[i]=max(s[i],s[i-1]);
}
for(int i=0;i<=n+1;++i)
{
for(int j=0;j<=m+1;++j)
c[i][j]=0;
}
for(int i=n;i;--i)
{
for(int j=1;j<=m;++j)
if (!a[i][j])
c[i][j]=c[i+1][j]+1;
else
c[i][j]=0;
c[i][m+1]=0;
}
for(int i=n;i;--i)
{
d=0;
for(int j=1;j<=m+1;++j)
{
while(d && c[i][st[d]]>=c[i][j])
{
sol=max(sol,s[i-1]+c[i][st[d]]*(st[d]-st[d-1]));
--d;
}
st[++d]=j;
}
}
}
int main ()
{
read ();
//solve (a, n, m);
solve (b, m, n);
ofstream fout ("bmatrix.out");
fout<<sol;
return 0;
}