Pagini recente » Cod sursa (job #1531804) | Cod sursa (job #704168) | Cod sursa (job #2861611) | Cod sursa (job #2532197) | Cod sursa (job #2447774)
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int n, m, a[205][205], s[205], Max, st[205], dr[205];
int max_sus[205], max_jos[205];
stack <int> d;
void fjaoisdfjl() {
max_sus[0] = max_jos[n + 1] = 0;
for (int l = 1; l <= n; ++l) {
max_sus[l] = max_sus[l - 1];
for (int c = 1; c <= m; ++c)
if (a[l][c] == 0)
++s[c];
else s[c] = 0;
for (int c = 1; c <= m; ++c) {
while (!d.empty() && s[d.top()] >= s[c])
d.pop();
if (!d.empty())
st[c] = d.top() + 1;
else st[c] = 1;
d.push(c);
}
while (!d.empty())
d.pop();
for (int c = m; c; --c) {
while (!d.empty() && s[d.top()] >= s[c])
d.pop();
if (!d.empty())
dr[c] = d.top() - 1;
else dr[c] = m;
d.push(c);
max_sus[l] = max(max_sus[l], (dr[c] - st[c] + 1) * s[c]);
}
while (!d.empty())
d.pop();
}
memset(s, 0, sizeof(s));
memset(dr, 0, sizeof(dr));
memset(st, 0, sizeof(st));
for (int l = n; l; --l) {
max_jos[l] = max_jos[l + 1];
for (int c = 1; c <= m; ++c)
if (a[l][c] == 0)
++s[c];
else s[c] = 0;
for (int c = 1; c <= m; ++c) {
while (!d.empty() && s[d.top()] >= s[c])
d.pop();
if (!d.empty())
st[c] = d.top() + 1;
else st[c] = 1;
d.push(c);
}
while (!d.empty())
d.pop();
for (int c = m; c; --c) {
while (!d.empty() && s[d.top()] >= s[c])
d.pop();
if (!d.empty())
dr[c] = d.top() - 1;
else dr[c] = m;
d.push(c);
max_jos[l] = max(max_jos[l], (dr[c] - st[c] + 1) * s[c]);
}
while (!d.empty())
d.pop();
}
memset(s, 0, sizeof(s));
memset(dr, 0, sizeof(dr));
memset(st, 0, sizeof(st));
for (int i = 1; i < n; ++i)
Max = max(Max, max_sus[i] + max_jos[i + 1]);
memset(max_sus, 0, sizeof(max_sus));
memset(max_jos, 0, sizeof(max_jos));
}
int main() {
fin >> n >> m;
char c;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> c;
a[i][j] = c - '0';
}
}
fjaoisdfjl();
fin.close();
ifstream fin("bmatrix.in");
fin >> n >> m;
char caracterfsjefdn;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> caracterfsjefdn;
a[j][i] = caracterfsjefdn - '0';
}
}
swap(n, m);
fjaoisdfjl();
fout << Max;
return 0;
}