Pagini recente » Cod sursa (job #2903024) | Cod sursa (job #572216) | Cod sursa (job #1888651) | Cod sursa (job #123572) | Cod sursa (job #1904040)
#include <cstdio>
#include <stack>
using namespace std;
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, int a[205][205]) {
/// 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() {
int a[205][205], b[205][205];
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);
}
//(1,1) (1,2)
//(2,1) (2,2)
//(1,1) (2,1)
//(1,2) (2,2)
/// Matricea b este transpusa lui A
for(int i = 1; i <= m; ++ i) {
for(int j = 1; j <= n; ++ j) {
b[i][j] = a[j][i];
}
}
///Fixez linia i1 si i2
int rasp = 0;
for(int i1 = 1; i1 < n; ++ i1) {
for(int i2 = i1 + 1; i2 <= n; ++ i2) {
int suma1;
suma1 = dreptunghi_Maxim(0, i1, m, a) + dreptunghi_Maxim(i1, i2, m, a);
if(suma1 > rasp) {
rasp = suma1;
}
}
}
for(int i1 = 1; i1 < m; ++ i1) {
for(int i2 = i1 + 1; i2 <= m; ++ i2) {
int suma2;
suma2 = dreptunghi_Maxim(0, i1, n, b) + dreptunghi_Maxim(i1, i2, n, b);
if(suma2 > rasp) {
rasp = suma2;
}
}
}
printf("%d\n", rasp);
return 0;
}