Pagini recente » Cod sursa (job #2489787) | Cod sursa (job #2341019) | Cod sursa (job #2202428) | Cod sursa (job #2344390) | Cod sursa (job #2634318)
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
int h[205];
char a[205][205];
int b[5][205],stiva[205],cnt;
int stanga[205],dreapta[205];
int n,m;
void rotator()
{
int rotate[205][205];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
rotate[j][n-i+1]=a[i][j];
}
}
swap(n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=rotate[i][j];
}
void solve(int dir)
{
for(int i=1;i<=204;i++)
h[i]=0;
for(int i=1;i<=n;i++)
{
b[dir][i]=b[dir][i-1];
for(int j=1;j<=m;j++)
{
if(a[i][j]=='0')
h[j]=h[j]+1;
else
h[j]=0;
}
stiva[0]=0;
cnt=0;
for(int j=1;j<=m;j++)
{
while(cnt && h[stiva[cnt]]>=h[j])
cnt--;
stanga[j]=stiva[cnt];
stiva[++cnt]=j;
}
stiva[0]=m+1;
cnt=0;
for(int j=m;j>0;j--)
{
while(cnt && h[stiva[cnt]]>=h[j])
cnt--;
dreapta[j]=stiva[cnt];
stiva[++cnt]=j;
}
for(int j=1;j<=m;j++)
{
if(b[dir][i]<h[j]*(dreapta[j]-stanga[j]-1))
b[dir][i]=h[j]*(dreapta[j]-stanga[j]-1);
}
}
}
int main()
{
in>>n>>m;
for(int i=1;i<+n;i++)
for(int j=1;j<=m;j++)
in>>a[i][j];
for(int i=1;i<=4;i++)
{
solve(i);
rotator();
}
int sol=0;
for(int i=1;i<=n;i++)
{
sol=max(sol,b[1][i]+b[3][n-i]);
}
for(int i=1;i<=m;i++)
{
sol=max(sol,b[2][i]+b[4][m-i]);
}
out<<sol;
return 0;
}