Pagini recente » Cod sursa (job #1807548) | Cod sursa (job #1187616) | Cod sursa (job #1940127) | Cod sursa (job #1187608) | Cod sursa (job #1295218)
#include <fstream>
#include <algorithm>
#define DIM 205
#define infile "bmatrix.in"
#define outfile "bmatrix.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int m, n;
char s[DIM][DIM], ss[DIM][DIM];
int a[DIM][DIM], D[DIM][DIM], v[DIM];
void DP() {
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
a[i][j] = a[i - 1][j] + s[i][j] - '0';
for (int i = m; i >= 1; --i) {
for (int j = i; j <= m; ++j) {
for (int k = 1; k <= n; ++k)
v[k] = a[j][k] - a[i - 1][k];
int Max = 0, len = 0;
for (int k = 1; k <= n; ++k) {
if (!v[k])
++len;
else {
Max = std::max(Max, len);
len = 0;
}
}
Max = std::max(Max, len);
D[i][j] = Max * (j - i + 1);
if (i < j) {
D[i][j] = std::max(D[i][j], D[i + 1][j]);
D[i][j] = std::max(D[i][j], D[i][j - 1]);
}
}
}
}
int main() {
int SOL = 0;
f >> m >> n;
for (int i = 1; i <= m; ++i)
f >> s[i] + 1;
DP();
for (int i = 1; i <= m; ++i)
SOL = std::max(SOL, D[1][i] + D[i + 1][m]);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
ss[j][m - i + 1] = s[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
s[i][j] = ss[i][j];
swap(n, m);
DP();
for (int i = 1; i <= m; ++i)
SOL = std::max(SOL, D[1][i] + D[i + 1][m]);
g << SOL;
return 0;
}
//Trust me, I'm the Doctor!