Pagini recente » Cod sursa (job #2751675) | Cod sursa (job #88129) | Cod sursa (job #2682216) | Cod sursa (job #747718) | Cod sursa (job #1557403)
#include <fstream>
#include <string.h>
#define Ndim 205
#define ush unsigned short int
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
ush N,M,sol,P[Ndim][Ndim],V[Ndim];
struct strct{ush val,poz;}ST[Ndim];
bool A[Ndim][Ndim],AUX[Ndim][Ndim];
char S[Ndim];
void read()
{
fin>>N>>M;
for(int i=1;i<=N;i++)
{
fin>>S+1;
for(int j=1;j<=M;j++)
A[i][j]=S[j]-'0';
}
}
void rotate_matrix_90()
{
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
AUX[j][N-i+1]=A[i][j];
memcpy(A,AUX,sizeof(A));
swap(M,N);
}
ush verif(int l)
{
ush i,j,vf=0,val1=0,val2=0,lpoz;
memset(V,0,sizeof(V));
for(i=1;i<=l;i++)
{
for(j=1;j<=M;j++)
{
V[j]=(V[j]+1)*(1-A[i][j]);
lpoz=j;
while(V[j]<ST[vf].val)
{
val1=max(val1,(ush)((j-ST[vf].poz)*ST[vf].val));
lpoz=ST[vf].poz;
vf--;
}
if(V[j]==ST[vf].val)
continue;
ST[++vf].val=V[j];
ST[vf].poz=lpoz;
}
V[j]=0;
while(V[j]<ST[vf].val)
{
val1=max(val1,(ush)((j-ST[vf].poz)*ST[vf].val));
vf--;
}
}
vf=0;
memset(V,0,sizeof(V));
for(i=l+1;i<=N;i++)
{
for(j=1;j<=M;j++)
{
V[j]=(V[j]+1)*(1-A[i][j]);
lpoz=j;
while(V[j]<ST[vf].val)
{
val2=max(val2,(ush)((j-ST[vf].poz)*ST[vf].val));
lpoz=ST[vf].poz;
vf--;
}
if(V[j]==ST[vf].val)
continue;
ST[++vf].val=V[j];
ST[vf].poz=lpoz;
}
V[j]=0;
while(V[j]<ST[vf].val)
{
val2=max(val2,(ush)((j-ST[vf].poz)*ST[vf].val));
vf--;
}
}
return val1+val2;
}
void solve()
{
int i,j;
for(i=1;i<N;i++)
sol=max(sol,verif(i));
rotate_matrix_90();
for(i=1;i<N;i++)
sol=max(sol,verif(i));
}
void print()
{
fout<<sol;
}
int main()
{
read();
solve();
print();
return 0;
}