Pagini recente » Cod sursa (job #1135191) | Cod sursa (job #1825805) | Cod sursa (job #1213343) | Cod sursa (job #2121737) | Cod sursa (job #1903897)
#include <cstdio>
#include <stack>
using namespace std;
int a[205][205];
int st[205], dr[205], v[205];
stack <int> stiva;
void golesc_Stiva() {
while(!stiva.empty()) {
stiva.pop();
}
}
int dreptunghi_Maxim(int i1, int i2, int n) {
/// O(n)
/// [i1 - 1, i2]
/// Vector de inaltimi
v[0] = v[n + 1] = -1;
int h;
h = i2 - i1;
for(int j = 1; j <= n; ++ j) {
if(a[i2][j] > h)
v[j] = h;
else
v[j] = a[i2][j];
}
/// Stanga
golesc_Stiva();
stiva.push(0);
for(int i = 1; i <= n; ++ i) {
while(v[stiva.top()] >= v[i]) {
stiva.pop();
}
st[i] = stiva.top();
stiva.push(i);
}
/// Dreapta
golesc_Stiva();
stiva.push(n + 1);
for(int i = n; i >= 1; -- i) {
while(v[stiva.top()] >= v[i]) {
stiva.pop();
}
dr[i] = stiva.top();
stiva.push(i);
}
/// Raspuns
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);
///Citire matrice + Suma de 0 pe coloana
char c;
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= m; ++ j) {
c = getc(stdin);
a[i][j] = 1 - (c - '0');
if(a[i][j] == 1)
a[i][j] += a[i - 1][j];
}
c = getc(stdin);
}
/*/// Debug-Open
printf("%d", dreptunghi_Maxim(0, 2, m) + dreptunghi_Maxim(2, 5, m));
return 0;
/// Debug-Close */
///Fixez linia i1 si i2
int rasp = 0;
for(int i1 = 1; i1 < n; ++ i1) {
for(int i2 = i1 + 1; i2 <= n; ++ i2) {
int suma;
suma = dreptunghi_Maxim(0, i1, m) + dreptunghi_Maxim(i1, i2, m);
if(suma > rasp) {
rasp = suma;
}
}
}
printf("%d\n", rasp);
return 0;
}