Pagini recente » Cod sursa (job #2248576) | Cod sursa (job #3321792) | Cod sursa (job #3348378) | Cod sursa (job #2347337) | Cod sursa (job #3312197)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX = 200;
int n, m;
bool a[NMAX + 1][NMAX + 1];
bool b[NMAX + 1][NMAX + 1];
int prefix_max_area[NMAX + 1];
int suffix_max_area[NMAX + 2];
int v[NMAX + 1];
int st[NMAX + 1], ind_st;
int l[NMAX + 1], r[NMAX + 1];
int get_max_area(int a[], int n) {
for(int i = 1; i <= n; i++) {
l[i] = r[i] = 0;
}
ind_st = 0;
for(int i = 1; i <= n; i++) {
while(ind_st >= 1 && a[st[ind_st]] >= a[i]) {
ind_st--;
}
l[i] = (!ind_st ? 0 : st[ind_st]);
st[++ind_st] = i;
}
ind_st = 0;
for(int i = n; i >= 1; i--) {
while(ind_st >= 1 && a[st[ind_st]] >= a[i]) {
ind_st--;
}
r[i] = (!ind_st ? n + 1 : st[ind_st]);
st[++ind_st] = i;
}
int max_area = 0;
for(int i = 1; i <= n; i++) {
max_area = max(max_area, (r[i] - l[i] - 1) * a[i]);
}
return max_area;
}
int get_answer(bool a[NMAX + 1][NMAX + 1], int n, int m) {
for(int j = 1; j <= m; j++) {
v[j] = 0;
}
for(int i = 0; i <= n; i++) {
prefix_max_area[i] = 0;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(!a[i][j]) {
v[j]++;
}
else {
v[j] = 0;
}
}
prefix_max_area[i] = max(prefix_max_area[i - 1], get_max_area(v, m));
}
for(int j = 1; j <= m; j++) {
v[j] = 0;
}
for(int i = 1; i <= n + 1; i++) {
suffix_max_area[i] = 0;
}
for(int i = n; i >= 1; i--) {
for(int j = 1; j <= m; j++) {
if(!a[i][j]) {
v[j]++;
}
else {
v[j] = 0;
}
}
suffix_max_area[i] = max(suffix_max_area[i + 1], get_max_area(v, m));
}
int answer = 0;
for(int i = 1; i < n; i++) {
answer = max(answer, prefix_max_area[i] + suffix_max_area[i + 1]);
}
return answer;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char x;
fin >> x;
a[i][j] = x - '0';
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
b[j][i] = a[i][j];
}
}
fout << max(get_answer(a, n, m), get_answer(b, m, n)) << '\n';
return 0;
}