Pagini recente » Cod sursa (job #1108890) | Cod sursa (job #1543450) | Cod sursa (job #1649180) | Cod sursa (job #50433) | Cod sursa (job #2134332)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e2;
int mat[MAXN + 2][MAXN + 2], aux[MAXN + 2][MAXN + 2], dp[4][MAXN + 2], num[MAXN + 2], n, m;
pair <int, int> stk[MAXN];
inline void solve(int n, int m, int wh) {
memset(num, 0, sizeof num);
for (int i = 1; i <= n; ++i) {
int st = -1;
mat[i][m + 1] = 0;
for (int j = 1; j <= m + 1; ++j) {
num[j] = mat[i][j] * (num[j] + 1);
int len = 0;
while (st >= 0 && stk[st].first >= num[j]) {
len += stk[st--].second;
dp[wh][i] = max(dp[wh][i], len * stk[st + 1].first);
}
stk[++st] = {num[j], len + 1};
}
}
}
inline void roootate(int& n, int& m) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
aux[i][j] = mat[i][j];
for (int i = m; i > 0; --i)
for (int j = 1; j <= n; ++j)
mat[m - i + 1][j] = aux[j][i];
swap(n, m);
}
int main()
{
ifstream fin("bmatrix.in");
fin >> n >> m;
for (int i = 1; i <= n; ++i) {
string s;
fin >> s;
for (int j = 1; j <= m; ++j)
mat[i][j] = '1' - s[j - 1];
}
fin.close();
for (int i = 0; i < 4; ++i) {
solve(n, m, i);
roootate(n, m);
}
int ans = 0;
for (int i = 1; i < n; ++i)
ans = max(ans, dp[0][i] + dp[2][n - i]);
for (int i = 1; i < m; ++i)
ans = max(ans, dp[1][i] + dp[3][m - i]);
ofstream fout("bmatrix.out");
fout << ans;
fout.close();
return 0;
}