Pagini recente » Cod sursa (job #2292525) | Cod sursa (job #164561) | Cod sursa (job #2631632) | Cod sursa (job #1710572) | Cod sursa (job #2430427)
#include <bits/stdc++.h>
#define Dim 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M,dp[6][Dim][Dim][Dim],B[6][Dim],ans;
char A[Dim][Dim];
int main()
{
f>>N>>M; f.get();
for(int i=1;i<=N;i++,f.get())
for(int j=1;j<=M;j++) f>>A[i][j];
for(int i=N;i>=1;i--)
{
int reper=0;
for(int j=M;j>=1;j--)
if(A[i][j]=='0')
{
reper++;
for(int k=1;k<=reper;k++)
dp[1][i][j][k]=dp[1][i+1][j][k]+k,
B[1][i]=max(B[1][i],max(B[1][i+1],dp[1][i][j][k]));
}
else
{
B[1][i]=max(B[1][i],B[1][i+1]);
reper=0;
}
}
for(int i=1;i<=N;i++)
{
int reper=0;
for(int j=1;j<=M;j++)
if(A[i][j]=='0')
{
reper++;
for(int k=1;k<=reper;k++)
dp[2][i][j][k]=dp[2][i-1][j][k]+k,
B[2][i]=max(B[2][i],max(B[2][i-1],dp[2][i][j][k]));
}
else
{
B[2][i]=max(B[2][i],B[2][i-1]);
reper=0;
}
}
for(int j=1;j<=M;j++)
{
int reper=0;
for(int i=1;i<=N;i++)
if(A[i][j]=='0')
{
reper++;
for(int k=1;k<=reper;k++)
dp[3][i][j][k]=dp[3][i][j-1][k]+k,
B[3][j]=max(B[3][j],max(B[3][j-1],dp[3][i][j][k]));
}
else
{
B[3][j]=max(B[3][j],B[3][j-1]);
reper=0;
}
}
for(int j=M;j>=1;j--)
{
int reper=0;
for(int i=1;i<=N;i++)
if(A[i][j]=='0')
{
reper++;
for(int k=1;k<=reper;k++)
dp[4][i][j][k]=dp[4][i][j][k]+k,
B[4][j]=max(B[4][j],max(B[4][j+1],dp[4][i][j][k]));
}
else
{
B[4][j]=max(B[4][j],B[4][j+1]);
reper=0;
}
}//cout<<'\n'<<'\n'<<dp[1][6][1][2]<<'\n';
// cout<<B[2][6]<<" "<<dp[1][1][3][2]<<'\n';
for(int i=1;i<N;i++) ans=max(ans,B[2][i]+B[1][i+1]); //cout<<B[2][i]<<" "<<B[1][i+1]<<" "<<i<<'\n';}
for(int j=1;j<M;j++) ans=max(ans,B[3][j]+B[4][j+1]);
g<<ans;
return 0;
}