Pagini recente » Cod sursa (job #2984395) | Cod sursa (job #228662) | Cod sursa (job #254221) | Cod sursa (job #196547) | Cod sursa (job #2930393)
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
int n,m,a[205][205],h[205][205],up[205],down[205];
int st[205],dr[205];
int ans;
int aux[205][205];
int main()
{
in >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char ch;
in >> ch;
if (ch == '1')
a[i][j] = 1;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
h[i][j] = 0;
else
h[i][j] = 1 + h[i - 1][j];
}
}
for (int i = 1; i <= n; i++)
{
stack<int>s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
dr[s.top()] = j - 1,s.pop();
s.push(j);
}
while (!s.empty())
dr[s.top()] = m,s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
st[s.top()] = j + 1,s.pop();
s.push(j);
}
while (!s.empty())
st[s.top()] = 1,s.pop();
int amax = 0;
for (int j = 1; j <= m; j++)
amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
up[i] = max(up[i - 1],amax);
}
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
h[i][j] = 0;
else
h[i][j] = 1 + h[i + 1][j];
}
}
for (int i = n; i >= 1; i--)
{
stack<int>s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
dr[s.top()] = j - 1,s.pop();
s.push(j);
}
while (!s.empty())
dr[s.top()] = m,s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
st[s.top()] = j + 1,s.pop();
s.push(j);
}
while (!s.empty())
st[s.top()] = 1,s.pop();
int amax = 0;
for (int j = 1; j <= m; j++)
amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
down[i] = max(down[i + 1],amax);
}
for (int i = 1; i <= n; i++)
ans = max(ans,up[i] + down[i + 1]);
for (int i = 1; i <= 200; i++)
for (int j = 1; j <= 200; j++)
h[i][j] = 0;
for (int i = 1; i <= 200; i++)
up[i] = down[i] = 0;
for (int i = 1; i <= 200; i++)
st[i] = dr[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
aux[j][i] = a[i][j];
swap(n,m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = aux[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
h[i][j] = 0;
else
h[i][j] = 1 + h[i - 1][j];
}
}
for (int i = 1; i <= n; i++)
{
stack<int>s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
dr[s.top()] = j - 1,s.pop();
s.push(j);
}
while (!s.empty())
dr[s.top()] = m,s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
st[s.top()] = j + 1,s.pop();
s.push(j);
}
while (!s.empty())
st[s.top()] = 1,s.pop();
int amax = 0;
for (int j = 1; j <= m; j++)
amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
up[i] = max(up[i - 1],amax);
}
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
h[i][j] = 0;
else
h[i][j] = 1 + h[i + 1][j];
}
}
for (int i = n; i >= 1; i--)
{
stack<int>s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
dr[s.top()] = j - 1,s.pop();
s.push(j);
}
while (!s.empty())
dr[s.top()] = m,s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and h[i][s.top()] > h[i][j])
st[s.top()] = j + 1,s.pop();
s.push(j);
}
while (!s.empty())
st[s.top()] = 1,s.pop();
int amax = 0;
for (int j = 1; j <= m; j++)
amax = max(amax,h[i][j] * (dr[j] - st[j] + 1));
down[i] = max(down[i + 1],amax);
}
for (int i = 1; i <= n; i++)
ans = max(ans,up[i] + down[i + 1]);
out << ans;
return 0;
}