Pagini recente » Cod sursa (job #1180198) | Cod sursa (job #787048)
Cod sursa(job #787048)
#include <iostream>
#include <fstream>
#include <stack>
#define DN 205
#define x first
#define y second
using namespace std;
typedef pair<int,int> per;
int n,m,h[DN],sol;
stack<per> s;
char mt[DN][DN];
int fa(int x1, int y1, int x2, int y2) {
int ret=0;
for(int i=y1-1; i<=y2+1; ++i) h[i]=0;
for(int i=x1; i<=x2; ++i) {
for(int j=y1; j<=y2; ++j) {
if('0'==mt[i][j]) ++h[j];
else h[j]=0;
}
s.push(make_pair(0,1));
for(int j=y1; j<=y2+1; ++j) {
ret=max(ret,h[j]);
int lst=j;
for(;s.size() && s.top().x>=h[j];s.pop()) {
ret=max(ret,s.top().x*(j-s.top().y));
lst=s.top().y;
}
s.push(make_pair(h[j],lst));
}
}
for(;s.size();s.pop());
return ret;
}
int main()
{
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
f>>n>>m;
for(int i=1; i<=n; ++i) f>>mt[i]+1;
int lm=m/2;
for(int i=1; i<=lm; ++i) sol=max(sol,fa(1,1,n,i)+fa(1,i+1,n,m));
lm=n/2;
for(int i=1; i<=lm; ++i) sol=max(sol,fa(1,1,i,m)+fa(i+1,1,n,m));
g<<sol;
return 0;
}