Pagini recente » Cod sursa (job #2792513) | Cod sursa (job #2570370)
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int hsus[N][N];
int hjos[N][N];
char mat[N][N];
int stv[N];
int st[N];
int skyline(int v[],int n){
int vf=0;
stv[0]=0;
for(int i=1;i<=n;i++){
while(vf>0 && v[i]<=v[stv[vf]])
vf--;
st[i]=stv[vf];
stv[++vf]=i;
}
int ans=0;
vf=0;
stv[vf]=n+1;
for(int i=n;i>=1;i--){
while(vf>0 && v[i]<=v[stv[vf]])
vf--;
int dr=stv[vf];
ans=max(ans,(dr-st[i]-1)*v[i]);
stv[++vf]=i;
}
return ans;
}
int main()
{
FILE*fin,*fout;
fin=fopen("bmatrix.in","r");
fout=fopen("bmatrix.out","w");
int n,m;
fscanf(fin,"%d%d ",&n,&m);
for(int i=1;i<=n;i++){
fgets(mat[i]+1,N,fin);
for(int j=1;j<=m;j++)
mat[i][j]-='0';
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mat[i][j]==0){
hsus[i][j]=hsus[i-1][j]+1;
}
else
hsus[i][j]=0;
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(mat[i][j]==0){
hjos[i][j]=hjos[i+1][j]+1;
}
else
hjos[i][j]=0;
}
}
int ans=0;
for(int lin=1;lin<=n;lin++){
int anssus=0;
for(int i=1;i<=lin;i++){
anssus=max(anssus,skyline(hsus[i],m));
}
int ansjos=0;
for(int i=lin+1;i<=n;i++){
ansjos=max(ansjos,skyline(hjos[i],m));
}
ans=max(ans,anssus+ansjos);
}
fprintf(fout,"%d",ans);
return 0;
}