Pagini recente » Cod sursa (job #1564733) | Cod sursa (job #2651791) | Cod sursa (job #1093743) | Cod sursa (job #381585) | Cod sursa (job #1324631)
#include <iostream>
#include <fstream>
#define N 201
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("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 Drept1(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 Drept2(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()
{
fin>>n>>m;
for(i=1;i<=n;++i)
{
fin>>(s+1);
for(j=1;j<=m;++j)
{
if(s[j]=='0')
a[i][j]=a[i-1][j]+1; ///i coloana, j linia
}
}
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,Drept1(1,i-1)+Drept1(i,n));
for(j=2;j<=m;++j)
sol=max(sol,Drept2(1,j-1)+Drept2(j,m));
fout<<sol<<'\n';
fin.close();
fout.close();
return 0;
}