Pagini recente » Cod sursa (job #1502492) | Cod sursa (job #615769) | Cod sursa (job #2323158) | Cod sursa (job #2479381) | Cod sursa (job #2812921)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
stack <pair <int, int> >st;
int n,m,ans;
char a[205][205];
char b[205][205];
int s1[205][205];
int s2[205][205];
int v[205];
int lft[205];
int rgt[205];
int dp1[205],dp2[205];
void read()
{
fin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fin>>a[i][j];
b[j][i]=a[i][j];
}
}
}
void partiale(char a[205][205])
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[j][i]=='0')
{
s1[j][i]=s1[j-1][i]+1;
}
else
{
s1[j][i]=0;
}
}
for(int j=n;j>=1;j--)
{
if(a[j][i]=='0')
{
s2[j][i]=s2[j+1][i]+1;
}
else
{
s2[j][i]=0;
}
}
}
}
int getMaxVal()
{
while(!st.empty())
{
st.pop();
}
st.push(make_pair(-1,0));
for(int i=1;i<=m;i++)
{
while(!st.empty() && v[i]<=st.top().first)
st.pop();
lft[i]=i-st.top().second-1;
st.push(make_pair(v[i],i));
}
while(!st.empty())
{
st.pop();
}
st.push(make_pair(-1,m+1));
for(int i=m;i>=1;i--)
{
while(!st.empty() && v[i]<=st.top().first)
st.pop();
rgt[i]=st.top().second-i-1;
st.push(make_pair(v[i],i));
}
int maxim=0;
for(int i=1;i<=m;i++)
{
maxim=max(maxim,(lft[i]+rgt[i]+1)*v[i]);
}
return maxim;
}
void solve()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
v[j]=s1[i][j];
}
dp1[i]=max(dp1[i-1],getMaxVal());
}
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
v[j]=s2[i][j];
}
dp2[i]=max(dp2[i+1],getMaxVal());
}
for(int i=1;i<=n;i++)
{
ans=max(ans,dp1[i]+dp2[i+1]);
}
for(int i=1;i<=n;i++)
{
dp1[i]=dp2[i]=0;
}
}
int main()
{
read();
partiale(a);
solve();
swap(n,m);
partiale(b);
solve();
fout<<ans;
return 0;
}