Pagini recente » Cod sursa (job #1763913) | Cod sursa (job #677990) | Cod sursa (job #566302) | Cod sursa (job #1969543) | Cod sursa (job #1189112)
#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];
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);
}
}
maxim=-1;
for (i=2;i<=n-1;i++)
maxim=max(maxim,dp[1][i]+dp[i][n]);
fout<<maxim<<"\n";
}
int main()
{
Citire();
Preprocesare();
DP();
return 0;
}