Pagini recente » Cod sursa (job #1189353) | Cod sursa (job #2370719) | Cod sursa (job #1662030) | Cod sursa (job #2313238) | Cod sursa (job #2242280)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char a[202][202],b[202][202];
int m,n,h[202][202],st[202],dmax[4][202],d;
void amax()
{
int i,j,v,arie;
for(j=1;j<=n;j++)
{
v=0;
for(i=1;i<=m;i++)
{
while(v>0&&h[i][j]<=h[st[v]][j])
{
arie=h[st[v]][j]*(i-1-st[v-1]);
dmax[d][i-1]=max(dmax[d][i-1],arie);
dmax[d][st[v]]=max(dmax[d][st[v]],h[st[v]][j]*(st[v]-st[v-1]));
v--;
}
st[++v]=i;
}
while(v>0)
{
arie=h[st[v]][j]*(m-st[v-1]);
dmax[d][m]=max(dmax[d][m],arie);
dmax[d][st[v]]=max(dmax[d][st[v]],h[st[v]][j]*(st[v]-st[v-1]));
v--;
}
}
for(i=2;i<=m;i++)
dmax[d][i]=max(dmax[d][i],dmax[d][i-1]);
}
void rotire()
{
int i,j;
for(i=0;i<=201;i++)
for(j=0;j<=201;j++)
h[i][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
b[j][m-i+1]=a[i][j];
swap(m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
a[i][j]=b[i][j];
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
if(a[i][j]=='0')
h[i][j]=h[i][j-1]+1;
}
}
int main()
{
int i,j,sol=0,x;
f>>m>>n;
f.get();
for(i=1;i<=m;i++)
f.getline(a[i]+1,201);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
if(a[i][j]=='0')
h[i][j]=h[i][j-1]+1;
}
d=0;
amax();
rotire();
d=1;
amax();
rotire();
d=2;
amax();
rotire();
d=3;
amax();
rotire();
for(i=0;i<m;i++)
{
x=dmax[0][i]+dmax[2][m-i];
if(x>sol)
sol=x;
}
for(i=0;i<n;i++)
{
x=dmax[1][i]+dmax[3][n-i];
if(x>sol)
sol=x;
}
g<<sol;
return 0;
}