Pagini recente » Cod sursa (job #503982) | Cod sursa (job #1216412) | Cod sursa (job #1220092) | Cod sursa (job #76147) | Cod sursa (job #2919062)
#include <bits/stdc++.h>
#define nmax 205
#define rf(i,a) for(int i=a-1;i>=0;i--)
#define fr(i,a) for(int i=0;i<a;i++)
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
bool mt[nmax][nmax];
int n,m;
int st[nmax],dr[nmax];
int stk[nmax],k;
int col[nmax];
int beach(const int &l)
{
k=0;
fr(i,l)
{
while(k>0&&col[stk[k-1]]>=col[i]) k--;
st[i]=k==0?-1:stk[k-1];
stk[k++]=i;
}
k=0;
rf(i,l)
{
while(k>0&&col[stk[k-1]]>=col[i]) k--;
dr[i]=k==0?l:stk[k-1];
stk[k++]=i;
}
int mx=0;
fr(i,l)
{
mx=max(mx,col[i]*(dr[i]-st[i]-1));
}
return mx;
}
void solveside(int *v, int side)
{
int a,b,c;
switch(side)
{
case 0:
a=0; b=n;
c=m;
break;
case 1:
a=n-1; b=-1;
c=m;
break;
case 2:
a=0; b=m;
c=n;
break;
default:
a=m-1; b=-1;
c=n;
}
fr(j,c)
{
col[j]=0;
}
for(int i=a;i!=b;i=i+1-(2)*(a>b))
{
fr(j,c)
{
bool nt=side>1?mt[j][i]:mt[i][j];
col[j]=(col[j]+nt)*nt;
}
if(i!=a) v[i]=max(v[a>b?i+1:i-1], beach(c));
else v[i]=beach(c);
}
}
int ans()
{
int up[nmax],dwn[nmax],lef[nmax],rig[nmax];
solveside(up,0);
solveside(dwn,1);
solveside(lef,2);
solveside(rig,3);
int mx=dwn[0];
fr(i,n-1)
{
mx=max(mx,up[i]+dwn[i+1]);
}
mx=max(mx,up[n-1]);
mx=max(mx,lef[0]);
fr(i,m-1)
{
mx=max(mx,lef[i]+rig[i+1]);
}
mx=max(mx,lef[m-1]);
return mx;
}
int main()
{
f>>n>>m;
string a;
fr(i,n)
{
f>>a;
fr(j,m)
{
mt[i][j]=(a[j]=='0');
//cout<<mt[i][j]<<' ';
}
//cout<<'\n';
}
g<<ans()<<'\n';
return 0;
}