Pagini recente » Cod sursa (job #2645248) | Cod sursa (job #1693915) | Cod sursa (job #2339658) | Cod sursa (job #609800) | Cod sursa (job #2409981)
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
int n, m, a[210][210], s[210][210], dpo[210][210], dpv[210][210];
char c;
int main() {
in >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
in >> c, a[i][j] = (c - '0' ? -4e4 : 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
for (int i = 1; i <= n; i++)
for (int j = i; j > 0; j--) {
int mn = 0;
for (int k = 1; k <= m; k++) {
dpv[j][i] = max(dpv[j][i], s[i][k] - s[j - 1][k] - mn);
mn = min(mn, s[i][k] - s[j - 1][k]);
}
if (i != j)
dpv[j][i] = max({dpv[j][i], dpv[j + 1][i], dpv[j][i - 1]});
}
for (int i = 1; i <= m; i++)
for (int j = i; j > 0; j--) {
int mn = 0;
for (int k = 1; k <= n; k++) {
dpo[j][i] = max(dpo[j][i], s[k][i] - s[k][j - 1] - mn);
mn = min(mn, s[k][i] - s[k][j - 1]);
}
if (i != j)
dpo[j][i] = max({dpo[j][i], dpo[j + 1][i], dpo[j][i - 1]});
}
int rs = 0;
for (int i = 1; i < n; i++)
rs = max(rs, dpv[1][i] + dpv[i + 1][n]);
for (int i = 1; i < m; i++)
rs = max(rs, dpo[1][i] + dpo[i + 1][m]);
out << rs;
return 0;
}