Pagini recente » Cod sursa (job #3151044) | Cod sursa (job #2158341) | Cod sursa (job #1628825) | Cod sursa (job #1606166) | Cod sursa (job #3289618)
#include <fstream>
#include <cassert>
#include <climits>
#include <stack>
#define ll long long
using namespace std;
const int NMAX = 200;
void buildstacks(int h[], int st[], int dr[], int n)
{
stack <int> stiva;
int i;
for (i = 1; i <= n; i++)
{
while (!stiva.empty() and h[stiva.top()] >= h[i])
stiva.pop();
if (stiva.empty())
st[i] = 0;
else
st[i] = stiva.top();
stiva.push(i);
}
while (!stiva.empty())
stiva.pop();
for (i = n; i >= 1; i--)
{
while (!stiva.empty() and h[stiva.top()] >= h[i])
stiva.pop();
if (stiva.empty())
dr[i] = n + 1;
else
dr[i] = stiva.top();
stiva.push(i);
}
}
int compute_res(int h[], int st[], int dr[], int n)
{
int i;
int ans = 0;
for (i = 1; i <= n; i++)
ans = max(ans, h[i] * (dr[i] - st[i] - 1));
return ans;
}
char s[NMAX + 1][NMAX + 1];
int preflin[NMAX + 1];
int suflin[NMAX + 2];
int prefcol[NMAX + 1];
int sufcol[NMAX + 2];
int h[NMAX + 1];
int st[NMAX + 1];
int dr[NMAX + 1];
int main()
{
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int n, m, i, j;
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
cin >> s[i][j];
}
int ans = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
if (s[i][j] == '0')
h[j]++;
else
h[j] = 0;
buildstacks(h, st, dr, m);
preflin[i] = max(preflin[i - 1], compute_res(h, st, dr, m));
}
ans = preflin[n];
for (i = 1; i <= m; i++)
h[i] = 0;
for (i = n; i >= 1; i--)
{
for (j = 1; j <= m; j++)
if (s[i][j] == '0')
h[j]++;
else
h[j] = 0;
buildstacks(h, st, dr, m);
suflin[i] = max(suflin[i + 1], compute_res(h, st, dr, m));
}
for (i = 1; i <= m; i++)
h[i] = 0;
for (j = 1; j <= m; j++)
{
for (i = 1; i <= n; i++)
if (s[i][j] == '0')
h[i]++;
else
h[i] = 0;
buildstacks(h, st, dr, n);
prefcol[j] = max(prefcol[j - 1], compute_res(h, st, dr, n));
}
for (i = 1; i <= n; i++)
h[i] = 0;
for (j = m; j >= 1; j--)
{
for (i = 1; i <= n; i++)
if (s[i][j] == '0')
h[i]++;
else
h[i] = 0;
buildstacks(h, st, dr, n);
sufcol[j] = max(sufcol[j + 1], compute_res(h, st, dr, n));
}
for (i = 1; i < n; i++)
ans = max(ans, preflin[i] + suflin[i + 1]);
for (i = 1; i < m; i++)
ans = max(ans, prefcol[i] + sufcol[i + 1]);
cout << ans;
}