Pagini recente » Cod sursa (job #1238870) | Cod sursa (job #192529) | Cod sursa (job #2827044) | Cod sursa (job #2401206) | Cod sursa (job #2020888)
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=205;
char s[nmax][nmax],nu[nmax][nmax];
int st[nmax],a[nmax],up[nmax],down[nmax],l[nmax],r[nmax];
int n,m,mx,i,j,u;
void build_dp(bool what)
{
u=0;st[0]=0;
for(j=1;j<=m;j++)
{
a[j]=(a[j]+1)*(s[i][j]=='0');
while(u>0&&a[j]<=a[st[u]])
u--;
l[j]=st[u];
u++;st[u]=j;
}
u=0;st[0]=m+1;
for(j=m;j>=1;j--)
{
while(u>0&&a[j]<a[st[u]])
u--;
r[j]=st[u];
u++;st[u]=j;
}
for(j=1;j<=m;j++)
{
if(what==0&&(r[j]-l[j]-1)*a[j]>up[i])
up[i]=(r[j]-l[j]-1)*a[j];
if(what==1&&(r[j]-l[j]-1)*a[j]>down[i])
down[i]=(r[j]-l[j]-1)*a[j];
}
}
void solve()
{
for(i=0;i<=n+1;i++)
up[i]=0;
for(i=1;i<=m;i++)
a[i]=0;
for(i=1;i<=n;i++)
{
build_dp(0);
}
for(i=0;i<=n+1;i++)
down[i]=0;
for(i=1;i<=m;i++)
a[i]=0;
for(i=n;i>=1;i--)
{
build_dp(1);
}
for(i=1;i<=n;i++)
up[i]=max(up[i],up[i-1]);
for(i=n;i>=1;i--)
down[i]=max(down[i],down[i+1]);
for(i=1;i<=n;i++)
if(up[i]+down[i+1]>mx)
mx=up[i]+down[i+1];
}
int main()
{
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>s[i][j];
solve();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
nu[j][i]=s[i][j];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
s[i][j]=nu[i][j];
swap(n,m);
solve();
g<<mx;
return 0;
}