Pagini recente » Borderou de evaluare (job #1567358) | Cod sursa (job #325454)
Cod sursa(job #325454)
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_N 203
bool A[MAX_N][MAX_N];
int N,M;
inline int drept_max(int l1, int l2, int c1, int c2)
{
int h[MAX_N], p = 0; // cate 0-uri am pe coloana i
int L[MAX_N][MAX_N], l[MAX_N][MAX_N];
int arie = 0;
int i,j;
memset(h,0,sizeof(h));
for(i=l1;i<=l2;++i) for(j=c1;j<=c2;++j) L[i][j] = l[i][j] = 0;
for(i=l1;i<=l2;++i)
for(j=c1, p = 0;j<=c2;++j)
{
if(A[i][j] == 1) { h[j] = 0; p = 0; continue; }
++p; h[j]++;
if(A[i-1][j-1] == 1)
{
if( h[j] > p ) { L[i][j] = h[j]; l[i][j] = 1; }
else { L[i][j] = 1; l[i][j] = p; }
arie = max(arie, L[i][j] * l[i][j]);
continue;
}
arie = max(arie, max(h[j],p));
L[i][j] = min(h[j], L[i-1][j-1] + 1);
l[i][j] = min(p, l[i-1][j-1] + 1);
if(j == 1) L[i][j] = h[j];
if(i == 1) l[i][j] = p;
arie = max(arie, L[i][j] * l[i][j]);
}
return arie;
}
int Amax;
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d %d\n",&N,&M);
int i,j,a1,a2; char x;
for(i=1;i<=N;++i)
{
for(j=1;j<=M;++j)
{
scanf("%c",&x);
A[i][j] = x - '0';
}
scanf("\n");
}
for(i = 2; i < N; ++i)
{
a1 = drept_max(1,i,1,M);
a2 = drept_max(i+1,N,1,M);
Amax = max(Amax,a1+a2);
}
for(i = 2; i< M; ++i)
{
a1 = drept_max(1,N, 1, i);
a2 = drept_max(1,N, i+1,M);
Amax = max(Amax, a1+a2);
}
printf("%d\n",Amax);
return 0;
}