Pagini recente » Cod sursa (job #2589632) | Cod sursa (job #2188182) | Cod sursa (job #1661154) | Cod sursa (job #1020911) | Cod sursa (job #2223630)
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
int n,m,i,j,A[205][205],H[205],Pst[205],pdr,rez,Dp[5][205],vr,Aux[205][205];
char S[205];
deque<int> Q;
void rotateA()
{
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
Aux[j][n-i+1]=A[i][j];
for(i=1; i<=m; i++)
for(j=1; j<=n; j++)
A[i][j]=Aux[i][j];
swap(n,m);
}
int main()
{
fi>>n>>m;
for(i=1; i<=n; i++)
{
fi>>S;
for(j=0; j<m; j++)
A[i][j+1]=S[j]-'0';
}
for(vr=1; vr<=4; vr++)
{
for(i=1; i<=m; i++)
H[i]=0;
for(i=1; i<=n; i++)
{
Dp[vr][i]=Dp[vr][i-1];
for(j=1; j<=m; j++)
H[j]=(A[i][j]==0)?(H[j]+1):0;
Q.clear();
for(j=1; j<=m; j++)
{
while(!Q.empty() && H[Q.back()]>=H[j])
Q.pop_back();
if(Q.empty())
Pst[j]=j-1;
else
Pst[j]=j-Q.back()-1;
Q.push_back(j);
}
Q.clear();
for(j=m; j>=1; j--)
{
while(!Q.empty() && H[Q.back()]>=H[j])
Q.pop_back();
if(Q.empty())
pdr=m-j+1;
else
pdr=Q.back()-j;
Dp[vr][i]=max(Dp[vr][i],H[j]*(Pst[j]+pdr));
Q.push_back(j);
}
}
rotateA();
}
for(i=1; i<n; i++)
rez=max(rez,Dp[1][i]+Dp[3][n-i]);
for(i=1; i<m; i++)
rez=max(rez,Dp[2][i]+Dp[4][m-i]);
fo<<rez<<"\n";
fi.close();
fo.close();
return 0;
}