Pagini recente » Cod sursa (job #47943) | Cod sursa (job #2283899) | Cod sursa (job #336990) | Cod sursa (job #508518) | Cod sursa (job #2504845)
#include <bits/stdc++.h>
using namespace std;
const int nmax=205;
bool v[nmax][nmax],aux[nmax][nmax];
int h[nmax][nmax],val[nmax],st[nmax],dr[nmax],sols[nmax],solj[nmax];
int n,m;
stack<int>sta;
void build_height()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(v[i][j]==0)
h[i][j]=h[i-1][j]+1;
else
h[i][j]=0;
}
void rotate90()
{
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
aux[i][j]=v[n-j+1][i];
swap(n,m);
memcpy(v,aux,sizeof(aux));
}
void rotate180()
{
rotate90();
rotate90();
}
void reset_stiva()
{
while(!sta.empty())
sta.pop();
}
void build_val(int l)
{
for(int i=1; i<=m; i++)
val[i]=h[l][i];
}
void build_st()
{
reset_stiva();
sta.push(1);
st[1]=0;
for(int i=2; i<=m; i++)
{
while(!sta.empty() && val[i] <= val[sta.top()])
sta.pop();
if(sta.empty())
st[i] = 0;
else
st[i] = sta.top();
sta.push(i);
}
}
void build_dr()
{
reset_stiva();
sta.push(m);
dr[m]=m+1;
for(int i=m-1; i>=1; i--)
{
while(!sta.empty() && val[i] <= val[sta.top()])
sta.pop();
if(sta.empty())
dr[i]=m+1;
else
dr[i]=sta.top();
sta.push(i);
}
}
int solve(int l)
{
build_val(l);
build_st();
build_dr();
int ans=0;
for(int i=1; i<=m; i++)
ans=max(ans,val[i]*(dr[i]-st[i]-1));
return ans;
}
int main()
{
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
char c;
int ans=0;
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
cin>>c;
v[i][j]=c-'0';
}
build_height();
for(int r=1; r<=n; r++)
sols[r]=max(sols[r-1],solve(r));
rotate180();
build_height();
for(int r=1; r<=n; r++)
solj[r]=max(solj[r-1],solve(r));
for(int i=1; i<n; i++)
ans=max(ans,sols[n-i]+solj[i]);
rotate90();
build_height();
for(int r=1; r<=n; r++)
sols[r]=max(sols[r-1],solve(r));
rotate180();
build_height();
for(int r=1; r<=n; r++)
solj[r]=max(solj[r-1],solve(r));
for(int i=1; i<n; i++)
ans=max(ans,sols[n-i]+solj[i]);
cout<<ans;
return 0;
}