Pagini recente » Cod sursa (job #1145433) | Cod sursa (job #1102439) | Cod sursa (job #160660) | Cod sursa (job #2283735) | Cod sursa (job #2206698)
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 210;
int n, m;
char a[NMAX][NMAX];
char b[NMAX][NMAX];
int dUp[NMAX][NMAX], dDown[NMAX][NMAX];
int st[NMAX], top;
int stg[NMAX], drp[NMAX];
int ans = 0;
void Read()
{
ifstream fin("bmatrix.in");
fin >> n >> m;
for (int i = 1;i <= n;++i)
fin >> (a[i] + 1);
fin.close();
}
void Initialize()
{
for (int i = 0;i <= n + 1;++i)
for (int j = 0;j <= m + 1;++j)
dUp[i][j] = dDown[i][j] = 0;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
a[i][j] == '0' ? dUp[i][j] = dUp[i - 1][j] + 1 : dUp[i][j] = 0;
for (int i = n;i >= 1;--i)
for (int j = 1;j <= m;++j)
a[i][j] == '0' ? dDown[i][j] = dDown[i + 1][j] + 1 : dDown[i][j] = 0;
}
void Rotate()
{
int p = n;
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= m;++j)
b[j][p] = a[i][j];
--p;
}
swap(n, m);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
a[i][j] = b[i][j];
for (int i = 1;i <= n;++i)
a[i][m + 1] = 0;
for (int j = 1;j <= m;++j)
a[n + 1][j] = 0;
}
void CreateStg(int line, bool ok)
{
if (ok)
dUp[line][0] = -1;
else
dDown[line][0] = -1;
top = 0;
st[0] = 0;
for (int i = 1;i <= m;++i)
{
if (ok)
while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
--top;
else
while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
--top;
stg[i] = i - st[top] - 1;
st[++top] = i;
}
}
void CreateDrp(int line, bool ok)
{
if (ok)
dUp[line][m + 1] = -1;
else
dDown[line][m + 1] = -1;
top = 0;
st[0] = m + 1;
for (int i = m;i >= 1;--i)
{
if (ok)
while (top > 0 && dUp[line][i] <= dUp[line][st[top]])
--top;
else
while (top > 0 && dDown[line][i] <= dDown[line][st[top]])
--top;
drp[i] = st[top] - i - 1;
st[++top] = i;
}
}
void Solve()
{
int aux1, aux2;
Initialize();
for (int i = 1;i < n;++i)
{
aux1 = aux2 = 0;
CreateStg(i, true);
CreateDrp(i, true);
for (int j = 1;j <= m;++j)
aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
CreateStg(i + 1, false);
CreateDrp(i + 1, false);
for (int j = 1;j <= m;++j)
aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
ans = max(ans, aux1 + aux2);
}
Rotate();
Initialize();
for (int i = 1;i < n;++i)
{
aux1 = aux2 = 0;
CreateStg(i, true);
CreateDrp(i, true);
for (int j = 1;j <= m;++j)
aux1 = max(aux1, (stg[j] + drp[j] + 1) * dUp[i][j]);
CreateStg(i + 1, false);
CreateDrp(i + 1, false);
for (int j = 1;j <= m;++j)
aux2 = max(aux2, (stg[j] + drp[j] + 1) * dDown[i + 1][j]);
ans = max(ans, aux1 + aux2);
}
}
void Write()
{
ofstream fout("bmatrix.out");
fout << ans << "\n";
fout.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}