Pagini recente » Cod sursa (job #918672) | Cod sursa (job #95562) | Cod sursa (job #855364) | Cod sursa (job #2063409) | Cod sursa (job #2332430)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");
const int NMAX = 205;
int n, m;
char a[NMAX][NMAX], b[NMAX][NMAX];
int h[NMAX];
int max_area_top[NMAX];
int max_area_bot[NMAX];
inline void maxi (int &a, int b) {
a = max (a, b);
}
inline int defaultVal1 (int pas, int n) {
return (pas == 1) ? 0 : n;
}
inline int defaultVal2 (int pas) {
return (pas == 1) ? 0 : -1;
}
void getArea (int pas, vi &v, int h[], int n) {
int st = 1;
if (pas == -1) st = n;
stack <int> stk;
for (int i = st; 1 <= i && i <= n; i += pas) {
while (!stk.empty() && h[stk.top()] >= h[i]) {
stk.pop();
}
v[i] = stk.empty() ? defaultVal1 (pas, n) : (stk.top() + defaultVal2 (pas));
stk.push (i);
}
while (!stk.empty()) stk.pop();
}
int getMaxArea (int h[], int n) {
stack <int> stk;
vi lft (n + 2, 0), rgt (n + 2, 0);
getArea (1, lft, h, n);
getArea (-1, rgt, h, n);
int ret = 0;
for (int i = 1; i <= n; ++i) {
maxi (ret, (rgt[i] - lft[i]) * h[i]);
}
return ret;
}
void calcMaxAreas (int pas, int max_area[]) {
int st = 1;
if (pas == -1) st = n;
memset (h, 0, sizeof (h));
for (int i = st; 1 <= i && i <= n; i += pas) {
for (int j = 1; j <= m; ++j) {
h[j] = a[i][j] == '0' ? h[j] + 1 : 0;
}
max_area[i] = max (max_area[i - pas], getMaxArea (h, m));
}
}
void rotateMatrix() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
b[j][n - i + 1] = a[i][j];
}
}
swap (n, m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = b[i][j];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif
f >> n >> m;
f.get();
for (int i = 1; i <= n; ++i) {
f.getline (a[i] + 1, NMAX);
}
int ans = 0;
for (int it = 1; it <= 2; ++it) {
memset (max_area_top, 0, sizeof (max_area_top));
memset (max_area_bot, 0, sizeof (max_area_bot));
calcMaxAreas (1, max_area_top);
calcMaxAreas (-1, max_area_bot);
for (int i = 1; i <= n; ++i) {
maxi (ans, max_area_top[i] + max_area_bot[i + 1]);
}
rotateMatrix();
}
g << ans << '\n';
f.close();
g.close();
#ifdef LOCAL_DEFINE
fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
return 0;
}