Pagini recente » Cod sursa (job #774112) | Cod sursa (job #2804613) | Cod sursa (job #1516659) | Cod sursa (job #914835) | Cod sursa (job #1912476)
#include <cstdio>
#include <stack>
using namespace std;
int lin[205][205], col[205][205];
int v[205], st[205], dr[205];
char s[205];
stack <int> mystack;
void golesc_stiva() {
while(!mystack.empty()) {
mystack.pop();
}
}
int drept_maxim(int i1, int i2, int n, int care) {
int h = i2 - i1;
if(care == 1) {
for(int i = 1; i <= n; ++ i) {
if(col[i2][i] > h) {
v[i] = h;
} else {
v[i] = col[i2][i];
}
}
} else {
for(int i = 1; i <= n; ++ i) {
if(lin[i][i2] > h) {
v[i] = h;
} else {
v[i] = lin[i][i2];
}
}
}
v[0] = v[n + 1] = -1;
golesc_stiva();
mystack.push(0);
for(int i = 1; i <= n; ++ i) {
while(v[i] <= v[mystack.top()]) {
mystack.pop();
}
st[i] = mystack.top();
mystack.push(i);
}
golesc_stiva();
mystack.push(n + 1);
for(int i = n; i >= 1; -- i) {
while(v[i] <= v[mystack.top()]) {
mystack.pop();
}
dr[i] = mystack.top();
mystack.push(i);
}
int rasp = 0;
for(int i = 1; i <= n; ++ i) {
int arie;
arie = v[i] * ((dr[i] - 1) - (st[i] + 1) + 1);
if(arie > rasp) {
rasp = arie;
}
}
return rasp;
}
int main() {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int n, m;
scanf("%d%d\n", &n, &m);
for(int i = 1; i <= n; ++ i) {
gets(s + 1);
for(int j = 1; j <= m; ++ j) {
if(s[j] == '0') {
lin[i][j] = lin[i][j - 1] + 1;
col[i][j] = col[i - 1][j] + 1;
}
}
}
int rasp = 0;
for(int i1 = 1; i1 < n; ++ i1) {
for(int i2 = i1; i2 <= n; ++ i2) {
int suma;
suma = drept_maxim(0, i1, m, 1) + drept_maxim(i1, i2, m, 1);
if(suma > rasp) {
rasp = suma;
}
}
}
for(int j1 = 1; j1 < m; ++ j1) {
for(int j2 = j1; j2 <= m; ++ j2) {
int suma;
suma = drept_maxim(0, j1, n, 0) + drept_maxim(j1, j2, n, 0);
if(suma > rasp) {
rasp = suma;
}
}
}
printf("%d", rasp);
return 0;
}