Pagini recente » Cod sursa (job #2115505) | Cod sursa (job #2162898) | Cod sursa (job #3336459) | Cod sursa (job #1037589) | Cod sursa (job #3352948)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 201
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int m,n;
int mat[MAX][MAX];
int h[MAX];
int area(int n, int h[]) {
stack<int> s;
int maxim=0;
vector<int> cop(n+2, 0);
for(int i=1; i<=n; i++) {
cop[i]=h[i];
}
for (int i=0; i<=n+1; i++) {
while (!s.empty() && cop[s.top()]>cop[i]) {
int lung=cop[s.top()];
s.pop();
int lat=i-s.top()-1;
maxim = max(maxim, lung*lat);
}
s.push(i);
}
return maxim;
}
int main() {
int i,j,maxim;
fin>>m>>n;
for (i=1; i<=m; i++) {
string s;
fin>>s;
for (j=1; j<=n; j++) {
mat[i][j]=s[j-1]-'0';
}
}
vector<int> up(m+2, 0), down(m+2, 0), st(n+2, 0), dr(n+2, 0);
for (i=1; i<=m; i++) {
for (j=1; j<=n; j++) {
if (mat[i][j]==0) {
h[j]++;
} else {
h[j]=0;
}
}
up[i]=max(up[i-1], area(n, h));
}
for (j=1; j<=MAX; j++) {
h[j]=0;
}
for (i=m; i>=1; i--) {
for (j=1; j<=n; j++) {
if (mat[i][j]==0) {
h[j]++;
} else {
h[j]=0;
}
}
down[i]=max(down[i+1], area(n, h));
}
maxim=0;
for (i=1; i<m; i++) {
maxim=max(maxim, up[i]+down[i+1]);
}
for (j=1; j<=MAX; j++) {
h[j]=0;
}
for (j=1; j<=n; j++) {
for (i=1; i<=m; i++) {
if (mat[i][j]==0) {
h[i]++;
} else {
h[i]=0;
}
}
st[j]=max(st[j-1], area(m, h));
}
for (j=1; j<=MAX; j++) {
h[j]=0;
}
for (j=n; j>=1; j--) {
for (i=1; i<=m; i++) {
if (mat[i][j]==0) {
h[i]++;
} else {
h[i]=0;
}
}
dr[j]=max(dr[j+1], area(m, h));
}
for (j=1; j<n; j++) {
maxim=max(maxim, st[j]+dr[j+1]);
}
fout<<maxim<<endl;
return 0;
}