Pagini recente » Cod sursa (job #2893943) | Cod sursa (job #2844770) | Cod sursa (job #1007262) | Cod sursa (job #3186641) | Cod sursa (job #1315612)
#include<cstdio>
int n,m,i,j,smax,x[210][210],sus[210],jos[210];
char s[210][210],t[210][210];
struct st{
int h;
int p;
}st[210];
FILE *f,*g;
int maxim(int a,int b){
if(a>b)
return a;
return b;
}
void calc(){
int i,j,nr,a,p,aux;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if(s[i][j]=='0')
x[i][j]=x[i-1][j]+1;
else
x[i][j]=0;
sus[i]=jos[i]=0;
}
for(i=1;i<=n;i++){
nr=0;
for(j=1;j<=m+1;j++){
if(x[i][j]>st[nr].h){
nr++;
st[nr].h=x[i][j];
st[nr].p=j;
}
else{
while(x[i][j]<=st[nr].h&&nr) {
a=(j-st[nr].p)*st[nr].h;
sus[i]=maxim(sus[i],a);
p=st[nr].p;
nr--;
}
if(x[i][j]>0){
nr++;
st[nr].p=p;
st[nr].h=x[i][j];
}
}
}
}
for(i=2;i<=n;i++){
sus[i]=maxim(sus[i],sus[i-1]);
}
for(i=1;i<=n/2;i++)
for(j=1;j<=m;j++){
aux=s[i][j];
s[i][j]=s[n-i+1][j];
s[n-i+1][j]=aux;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if(s[i][j]=='0')
x[i][j]=x[i-1][j]+1;
else
x[i][j]=0;
}
for(i=1;i<=n;i++){
nr=0;
for(j=1;j<=m+1;j++){
if(x[i][j]>st[nr].h){
nr++;
st[nr].h=x[i][j];
st[nr].p=j;
}
else{
while(x[i][j]<=st[nr].h&&nr) {
a=(j-st[nr].p)*st[nr].h;
jos[i]=maxim(jos[i],a);
p=st[nr].p;
nr--;
}
if(x[i][j]>0){
nr++;
st[nr].p=p;
st[nr].h=x[i][j];
}
}
}
}
for(i=2;i<=n;i++){
jos[i]=maxim(jos[i],jos[i-1]);
}
for(i=1;i<=n/2;i++){
aux=jos[i];
jos[i]=jos[n-i+1];
jos[n-i+1]=aux;
}
for(i=1;i<=n/2;i++){
for(j=1;j<=m;j++){
aux=s[i][j];
s[i][j]=s[n-i+1][j];
s[n-i+1][j]=aux;
}
}
}
int main(){
f=fopen("bmatrix.in","r");
g=fopen("bmatrix.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++){
fscanf(f,"%s",s[i]+1);
}
calc();
for(i=1;i<=n;i++){
smax=maxim(smax,sus[i]+jos[i+1]);
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
t[j][n-i+1]=s[i][j];
}
}
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
s[i][j]=t[i][j];
}
}
int aux=n;
n=m;
m=aux;
calc();
for(i=1;i<=n;i++){
smax=maxim(smax,sus[i]+jos[i+1]);
}
fprintf(g,"%d",smax);
fclose(f);
fclose(g);
return 0;
}