Pagini recente » Cod sursa (job #2941467) | Cod sursa (job #2791553) | Cod sursa (job #515742) | Cod sursa (job #2667039) | Cod sursa (job #3247706)
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <stack>
using namespace std;
ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");
int n, m, mat[205][205], pref_linie[205], pref_coloana[205], suf_linie[205], suf_coloana[205], st[205], dr[205], h[205], stiva[205], cnt;
void actst (int l)
{
stiva[0]=0;
for (int i=1;i<=l;i++)
{
while (stiva[0] && h[stiva[stiva[0]]]>=h[i])
{
stiva[0]--;
}
if (!stiva[0])
{
st[i]=0;
}
else st[i]=stiva[stiva[0]];
stiva[++stiva[0]]=i;
}
}
void actdr (int l)
{
stiva[0]=0;
for (int i=l;i>=1;i--)
{
while (stiva[0] && h[stiva[stiva[0]]]>=h[i])
{
stiva[0]--;
}
if (!stiva[0])
{
dr[i]=l+1;
}
else dr[i]=stiva[stiva[0]];
stiva[++stiva[0]]=i;
}
}
void skyline (int l)
{
actst (l);
actdr (l);
}
void actmx (int *v, int l, int ind, int coef)
{
v[ind]=v[ind+coef];
for (int i=1;i<=l;i++)
{
if (h[i]) v[ind]=max (v[ind], h[i]*(dr[i]-st[i]-1));
}
}
void reset_h ()
{
for (int i=1;i<=max (n, m);i++)
{
h[i]=0;
}
}
int main()
{
f >> n >> m;
for (int i=1;i<=n;i++)
{
string s;
f >> s;
for (int j=1;j<=m;j++)
{
mat[i][j]=s[j-1]-'0';
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
h[j]=(mat[i][j]==1?0:h[j]+1);
}
skyline (m);
actmx (pref_linie, m, i, -1);
}
reset_h ();
for (int i=n;i>=1;i--)
{
for (int j=1;j<=m;j++)
{
h[j]=(mat[i][j]==1?0:h[j]+1);
}
skyline (m);
actmx (suf_linie, m, i, 1);
}
reset_h ();
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
h[j]=(mat[j][i]==1?0:h[j]+1);
}
skyline (n);
actmx (pref_coloana, n, i, -1);
}
reset_h ();
for (int i=m;i>=1;i--)
{
for (int j=1;j<=n;j++)
{
h[j]=(mat[j][i]==1?0:h[j]+1);
}
skyline (n);
actmx (suf_coloana, n, i, 1);
}
int rasp=0;
for (int i=1;i<=n;i++)
{
rasp=max (rasp, pref_linie[i]+suf_linie[i+1]);
}
for (int i=1;i<=m;i++)
{
rasp=max (rasp, pref_coloana[i]+suf_coloana[i+1]);
}
g << rasp;
return 0;
}