Pagini recente » Cod sursa (job #2169352) | Cod sursa (job #1657640) | Istoria paginii runda/absenta/clasament | Cod sursa (job #1187553) | Cod sursa (job #1041353)
#include <fstream>
#include <cstring>
using namespace std;
char a[205][205];
int dp[205][205] , s[205][205] , n, m, sol = 0;
inline void Read()
{
ifstream f("bmatrix.in");
f >> n >> m;
for(register int i = 1;i <= n; ++i)
f>>(a[i]+1);
f.close();
}
inline void Rotate(char a[][205])
{
char C[205][205];
register int i, j;
memcpy(C,a,sizeof(C));
for(i = 1;i <= m; ++i)
for(j = 1;j <= n; ++j)
a[i][j] = C[j][m-i+1];
swap(n,m);
}
inline void Init()
{
register int i,j;
for(i = 1;i <= n;++i)
for(j = 1;j <= n; ++j)
dp[i][j] = -1;
}
inline int DP(const int i,const int j)
{
if(i>j)
return 0;
if(dp[i][j]>=0)
return dp[i][j];
dp[i][j] = max(DP(i+1,j),DP(i,j-1));
int best = 0;
for(int ind = 1;ind <= m; ++ind)
{
if(s[j][ind]-s[i-1][ind])
best = 0;
else
++best;
dp[i][j] = max(best*(j-i+1),dp[i][j]);
}
return dp[i][j];
}
inline void DP()
{
register int i,j;
for(i = 1;i <= n; ++i)
for(j = i;j <= n; ++j)
dp[i][j] = DP(i,j);
}
inline int Result()
{
register int best = 0, i;
for(i = 1;i < n;++i)
best = max(best,dp[1][i]+dp[i+1][n]);
return best;
}
inline void Partial_Sums()
{
register int i,j;
for(i = 1;i <= n; ++i)
for(j = 1;j <= m; ++j)
s[i][j] = s[i-1][j] + a[i][j] - '0';
}
inline void Solve()
{
Partial_Sums();
Init();
DP();
sol = Result();
Rotate(a);
Partial_Sums();
Init();
DP();
sol = max(sol,Result());
}
inline void Write()
{
ofstream g("bmatrix.out");
g<<sol<<"\n";
g.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}