Pagini recente » Cod sursa (job #1954678) | Cod sursa (job #1241098) | Cod sursa (job #163853) | Cod sursa (job #2407637) | Cod sursa (job #1837753)
#include <bits/stdc++.h>
#define MAXN 201
char mat[MAXN+1][MAXN+1];
char cop[MAXN+1][MAXN+1];
inline int getmax(int a,int b){
if(a<b) return b;
return a;
}
int stiv[MAXN+1],high[MAXN+1],len[MAXN+1];
int sl[MAXN+1],sr[MAXN+1];
inline int solve(int n,int m){
int ans,i,j,ist,l,p;
memset(sl,0,sizeof(sl));
memset(sr,0,sizeof(sr));
memset(high,0,sizeof(high));
for(i=1;i<=n;i++){
ist=-1;
for(j=1;j<=m;j++){
if(mat[i][j]==1)
high[j]=0;
else
high[j]++;
l=0;
while(ist>=0&&high[stiv[ist]]>=high[j]){
l+=len[ist];
if(sl[j]<l*high[stiv[ist]])
sl[j]=l*high[stiv[ist]];
ist--;
}
ist++;
stiv[ist]=j;
len[ist]=l+1;
p=ist;
l=0;
while(p>=0){
l+=len[p];
if(l*high[stiv[p]]>sl[j])
sl[j]=l*high[stiv[p]];
p--;
}
}
}
for(j=1;j<=m;j++)
sl[j]=getmax(sl[j-1],sl[j]);
memset(high,0,sizeof(high));
for(i=1;i<=n;i++){
ist=-1;
for(j=m;j>=1;j--){
if(mat[i][j]==1)
high[j]=0;
else
high[j]++;
l=0;
while(ist>=0&&high[stiv[ist]]>=high[j]){
l+=len[ist];
if(sr[j]<l*high[stiv[ist]])
sr[j]=l*high[stiv[ist]];
ist--;
}
ist++;
stiv[ist]=j;
len[ist]=l+1;
p=ist;
l=0;
while(p>=0){
l+=len[p];
if(l*high[stiv[p]]>sr[j])
sr[j]=l*high[stiv[p]];
p--;
}
}
l=0;
while(ist>=0){
l+=len[ist];
if(sr[1]<l*high[stiv[ist]])
sr[1]=l*high[stiv[ist]];
ist--;
}
}
for(j=m;j>=1;j--)
sr[j]=getmax(sr[j+1],sr[j]);
ans=0;
for(i=1;i<m;i++)
ans=getmax(ans,sl[i]+sr[i+1]);
return ans;
}
int main(){
FILE*fi,*fout;
int i,j,n,m,ans;
fi=fopen("bmatrix.in" ,"r");
fout=fopen("bmatrix.out" ,"w");
fscanf(fi,"%d %d " ,&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
mat[i][j]=fgetc(fi)-'0';
cop[i][j]=mat[i][j];
}
fgetc(fi);
}
ans=solve(n,m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
mat[m-j+1][i]=cop[i][j];
ans=getmax(ans,solve(m,n));
fprintf(fout,"%d" ,ans);
fclose(fi);
fclose(fout);
return 0;
}