Pagini recente » Cod sursa (job #496972) | Cod sursa (job #360843) | Cod sursa (job #192538) | Cod sursa (job #106594) | Cod sursa (job #2030244)
#include <iostream>
#include <memory.h>
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int NMAX = 200;
struct Data {
int val;
int sum;
};
int n, m, res;
int fv[1 + NMAX];
int dp[4][1 + NMAX];
bool v[1 + NMAX][1 + NMAX];
bool v2[1 + NMAX][1 + NMAX];
char s[2 * NMAX];
stack < Data > st;
void rotatemat() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
v2[j][n - i + 1] = v[i][j];
}
}
swap(n, m);
memcpy(v, v2, sizeof(v));
}
void solve(int z) {
fill(fv, fv + NMAX + 1, 0);
for(int i = 1; i <= n; i++) {
dp[z][i] = dp[z][i - 1];
for(int j = 1; j <= m + 1; j++) {
if(v[i][j] == 0 && j <= m)
fv[j]++;
else
fv[j] = 0;
int sum = 0;
while(!st.empty() && fv[j] <= st.top().val) {
Data from = st.top();
st.pop();
sum += from.sum;
dp[z][i] = max(dp[z][i], sum * from.val);
}
st.push({fv[j], sum + 1});
}
}
}
int main()
{
in >> n >> m;
in.get();
for(int i = 1; i <= n; i++) {
in.getline(s, 2 * NMAX);
for(int j = 0; j < m; j++) {
v[i][j + 1] = s[j] - '0';
}
}
for(int i = 0; i < 4; i++) {
solve(i);
rotatemat();
}
for(int i = 1; i <= n; i++) {
res = max(res, dp[0][i] + dp[2][n - i]);
}
for(int i = 1; i <= m; i++) {
res = max(res, dp[1][i] + dp[3][m - i]);
}
out << res << '\n';
in.close();
out.close();
return 0;
}