Pagini recente » Cod sursa (job #68123) | Cod sursa (job #743236) | Cod sursa (job #2897702) | Cod sursa (job #1231777) | Cod sursa (job #3162947)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, a[205][205], v[205], up[205], down[205], l[205], r[205], sol, st[205], dr[205], top, stv[205];
string s[205];
int Solve(int n)
{
int i, x, ans = 0;
top = 0;
stv[top] = 0;
v[0] = v[n + 1] = -1;
for (i = 1; i <= n; i++)
{
x = v[i];
while (top and v[stv[top]] >= x)
top--;
st[i] = i - stv[top] - 1;
stv[++top] = i;
}
top = 0;
stv[top] = n + 1;
for (i = n; i >= 1; i--)
{
x = v[i];
while (top and v[stv[top]] >= x)
top--;
dr[i] = stv[top] - i - 1;
stv[++top] = i;
}
for (i = 1; i <= n; i++)
ans = max(ans, v[i] * (st[i] + dr[i] + 1));
return ans;
}
void ResetV(int n)
{
for (int i = 1; i <= n; i++)
v[i] = 0;
}
int32_t main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= n; i++)
{
fin >> s[i];
s[i] = '%' + s[i];
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
if (s[i][j] == '0')
v[j]++;
else
v[j] = 0;
up[i] = max(up[i - 1], Solve(m));
}
ResetV(m);
for (i = n; i >= 1; i--)
{
for (j = 1; j <= m; j++)
if (s[i][j] == '0')
v[j]++;
else
v[j] = 0;
down[i] = max(down[i + 1], Solve(m));
}
ResetV(m);
for (j = 1; j <= m; j++)
{
for (i = 1; i <= n; i++)
if (s[i][j] == '0')
v[i]++;
else
v[i] = 0;
l[j] = max(l[j - 1], Solve(n));
}
ResetV(n);
for (j = m; j >= 1; j--)
{
for (i = 1; i <= n; i++)
if (s[i][j] == 0)
v[i]++;
else
v[i] = 0;
r[j] = max(r[j + 1], Solve(n));
}
for (i = 0; i <= n; i++)
sol = max(sol, up[i] + down[i + 1]);
for (i = 0; i <= m; i++)
sol = max(sol, l[i] + r[i + 1]);
fout << sol << "\n";
return 0;
}