Pagini recente » Cod sursa (job #295019) | Cod sursa (job #2284651) | Cod sursa (job #2439045) | Cod sursa (job #3207009) | Cod sursa (job #1678724)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int k,q[205],n,m,a[205][205],b[205][205],csus[205][205],cjos[205][205],st[205],dr[205],vsus[205][205],vjos[205][205];
int mxsus[205],mxjos[205],sol,sol1,sol2;
void Solve(int caz)
{ int i,j,mx=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if (!a[i][j]) csus[i][j]=csus[i-1][j]+1;
for(i=n;i>=1;i--)
for(j=1;j<=m;j++)
if (!a[i][j]) cjos[i][j]=cjos[i+1][j]+1;
for(i=1;i<=n;i++)
{
k=0;
for(j=1;j<=m;j++)
{ while(k && csus[i][q[k]]>=csus[i][j])
k--;
if (!k) st[j]=1; else st[j]=q[k]+1;
k++; q[k]=j;
}
k=0;
for(j=m;j>=1;j--)
{ while(k && csus[i][q[k]]>=csus[i][j])
k--;
if (!k) dr[j]=m; else dr[j]=q[k]-1;
k++; q[k]=j;
}
for(j=1;j<=m;j++)
vsus[i][j]=(dr[j]-st[j]+1)*csus[i][j];
}
for(i=1;i<=n;i++)
{
k=0;
for(j=1;j<=m;j++)
{ while(k && cjos[i][q[k]]>=cjos[i][j])
k--;
if (!k) st[j]=1; else st[j]=q[k]+1;
k++; q[k]=j;
}
k=0;
for(j=m;j>=1;j--)
{ while(k && cjos[i][q[k]]>=cjos[i][j])
k--;
if (!k) dr[j]=m; else dr[j]=q[k]-1;
k++; q[k]=j;
}
for(j=1;j<=m;j++)
vjos[i][j]=(dr[j]-st[j]+1)*cjos[i][j];
}
mx=0;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
mx=max(mx,vsus[i][j]);
mxsus[i]=mx;
}
mx=0;
for(i=n;i>=1;i--)
{for(j=1;j<=n;j++)
mx=max(mx,vjos[i][j]);
mxjos[i]=mx;
}
for(i=1;i<n;i++)
if (mxsus[i]>0 && mxjos[i+1]>0)
{ if (caz==1) sol1=max(sol1,mxsus[i]+mxjos[i+1]);
else sol2=max(sol2,mxsus[i]+mxjos[i+1]);
}
}
void Roteste()
{ int i,j,l=0,c=0;
for(i=n;i>=1;i--)
{ c++;
for(j=1;j<=m;j++)
b[j][c]=a[i][j];
}
swap(n,m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=b[i][j];
}
int main()
{ int i,j; char s[205];
f>>n>>m;
for(i=1;i<=n;i++)
{ f>>s;
for(j=1;j<=m;j++)
a[i][j]=s[j-1]-48;
}
Solve(1);
Roteste();
memset(st,0,sizeof(st));
memset(dr,0,sizeof(dr));
memset(cjos,0,sizeof(cjos));
memset(csus,0,sizeof(csus));
memset(mxjos,0,sizeof(mxjos));
memset(mxsus,0,sizeof(mxsus));
memset(vjos,0,sizeof(vjos));
memset(vsus,0,sizeof(vsus));
Solve(2);
sol=max(sol1,sol2);
g<<sol;
return 0;
}