Pagini recente » Cod sursa (job #2976506) | Cod sursa (job #1080443) | Cod sursa (job #3147042) | Cod sursa (job #2812498) | Cod sursa (job #3178236)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
bool v[205][205];
int r[205][205];
int n,m;
int largest_rect(bool v[205][205],int sn,int sm,int n,int m)
{
int maximum = 0;
memset(r,0,sizeof(r));
for(int i=sn; i<=n; i++)
{
vector <int> stk;
for(int j=sm; j<=m+1; j++)
{
if(v[i][j])
r[i][j]=0;
else
r[i][j]=r[i-1][j]+1;
if(j==m+1)
r[i][j]=0;
while(!stk.empty() && r[i][j]<=r[i][stk.back()])
{
int h = r[i][stk.back()];
stk.pop_back();
int w = j-1;
if(!stk.empty())
w-=stk.back();
else
w=w-sm+1;
if(maximum < h*w)
maximum=h*w;
}
stk.push_back(j);
}
}
return maximum;
}
int main()
{
fin>>n>>m;
for(int i=1; i<=n; i++)
{
char ch;
for(int j=1; j<=m; j++)
fin>>ch,v[i][j]=ch-'0';
}
int mxsol = 0;
for(int i=1;i<m;i++)
{
int s1 = largest_rect(v,1,1,n,i);
int s2 = largest_rect(v,1,i+1,n,m);
mxsol=max(mxsol,s1+s2);
}
for(int i=1;i<n;i++)
{
int s1 = largest_rect(v,1,1,i,m);
int s2 = largest_rect(v,i+1,1,n,m);
mxsol=max(mxsol,s1+s2);
}
fout<<mxsol;
}