Pagini recente » Cod sursa (job #2794090) | Cod sursa (job #555793) | Cod sursa (job #1883532) | Cod sursa (job #1182155) | Cod sursa (job #1189367)
#include<fstream>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int Nmax=205;
int n,m,sumepart[Nmax][Nmax],dp[Nmax][Nmax],M;
bool a[Nmax][Nmax];
char s[205];
inline void Citire()
{
int i,j;
fin>>n>>m;
for (i=1;i<=n;i++)
{
fin>>(s+1);
for (j=1;j<=m;j++)
a[i][j]=s[j]-'0';
}
}
inline void Preprocesare()
{
int i,j,nr,maxim;
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)
{
sumepart[i][j]=sumepart[i-1][j];
if (a[i][j]) sumepart[i][j]++;
}
for (i=1;i<=n;i++)
{
j=1;maxim=0;
while (j<=m)
{
while (j<=m && a[i][j]) j++;
nr=0;
while (j<=m && !a[i][j]) {nr++;j++;}
if (nr>maxim) maxim=nr;
}
dp[i][i+1]=maxim;
}
}
inline void DP()
{
int i,j,nr=1,maxim,c;
while (nr<=n-1)
{
nr++;
for (i=1;i<=n-nr+1;i++)
{
dp[i][i+nr]=max(dp[i+1][i+nr],dp[i][i+nr-1]);
j=1;maxim=0;
while (j<=m)
{
while (j<=m && sumepart[i+nr-1][j]>sumepart[i-1][j]) j++;
c=0;
while (j<=m && sumepart[i+nr-1][j]==sumepart[i-1][j]) {c+=nr;j++;}
if (c>maxim) maxim=c;
}
dp[i][i+nr]=max(dp[i][i+nr],maxim);
}
}
for (i=2;i<=n-1;i++)
M=max(M,dp[1][i]+dp[i][n]);
}
inline void Rotate()
{
int i,j,k=0,l,aux[Nmax][Nmax];
for (j=1;j<=m;j++)
{
k++;l=0;
for (i=n;i>=1;i--)
{
l++;
aux[k][l]=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()
{
Citire();
Preprocesare();
DP();
Rotate();
Preprocesare();
DP();
fout<<M<<"\n";
return 0;
}