Pagini recente » Cod sursa (job #726047) | Cod sursa (job #1976864) | Cod sursa (job #54591) | Cod sursa (job #2427749) | Cod sursa (job #2799481)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int s[205][205];
int n,m,d[205],st[205],dr[205],sus[205],jos[205];
int main()
{
char c;
fin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fin>>c;
s[i][j]=c-'0';
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]==0)
d[j]++; // cate 0-uri se afla pe colana j intre liniile 1-i
else d[j]=0;
int nr=0,h=2e9;
for(int k=j;k>=1;k--)
{
h=min(h,d[k]);
nr=max(nr,h*(j-k+1)); // nr = aria maxima a unui dreptunghi cu coltul dreapta jos i,j
}
sus[i]=max(max(sus[i-1],sus[i]),nr); // deasupra liniei i se obtine dreptunghi de arie maxima sus[i]
st[j]=max(max(st[j-1],st[j]),nr); // la stanga coloanei j se obtine dreptunghi de arie maxima st[i]
}
}
memset(d,0,sizeof(d));
for(int i=n;i>=1;i--)
{
for(int j=m;j>=1;j--)
{
if(s[i][j]==0)
d[j]++; // cate 0-uri se afla pe coloana j intre liniile i-n
else d[j]=0;
int nr=0,h=2e9;
for(int k=j;k<=m;k++)
{
h=min(h,d[k]);
nr=max(nr,h*(k-j+1)); // nr = aria maxima a unui dreptunghi cu coltul stanga sus i,j
}
jos[i]=max(max(jos[i-1],jos[i]),nr); // sub linia i se obtine dreptunghi de arie maxima jos[i]
dr[j]=max(max(dr[j-1],dr[j]),nr); // la dreapta coloanei j se obtine dreptunghi de arie maxima dr[i]
}
}
int sol=0;
for(int i=1;i<n;i++)sol=max(sol,sus[i]+jos[i+1]);
for(int j=1;j<m;j++)sol=max(sol,st[j]+dr[j+1]);
fout<<sol;
}