Pagini recente » Cod sursa (job #2251079) | Cod sursa (job #1723101) | Cod sursa (job #2419223) | Cod sursa (job #1674604) | Cod sursa (job #1401374)
#include <cstring>
#include <fstream>
#include <stack>
using namespace std;
const int MAX_N = 202;
int N, M, sol;
int H[MAX_N][MAX_N], D[MAX_N][MAX_N], dp[MAX_N][MAX_N];
char s[MAX_N];
bool A[MAX_N][MAX_N];
void read() {
ifstream f("bmatrix.in");
f >> N >> M;
for(int i = 1; i <= N; ++i) {
f >> s;
for(int j = 0; j < M; ++j)
if(s[j] == '0')
A[i][j + 1] = 1;
}
f.close();
}
void solveLine(int line, int v[], int n) {
stack < pair < int, int > > st;
for(int i = 1; i <= n; ++i) {
if(st.empty() || v[i] > st.top().first)
st.push(make_pair(v[i], 1));
else if(st.top().first == v[i])
++st.top().second;
else {
int cnt = 0;
while(!st.empty() && v[i] < st.top().first) {
cnt += st.top().second;
int top = st.top().first;
st.pop();
H[line][top] = max(H[line][top], cnt);
}
st.push(make_pair(v[i], cnt + 1));
}
}
int cnt = 0;
while(!st.empty()) {
cnt += st.top().second;
int top = st.top().first;
st.pop();
H[line][top] = max(H[line][top], cnt);
}
}
void compute() {
memset(H, 0, sizeof(H));
memset(D, 0, sizeof(D));
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j)
if(A[i][j])
D[i][j] = D[i - 1][j] + 1;
solveLine(i, D[i], M);
}
for(int i = 1; i <= N; ++i) {
for(int j = i; j >= 1; --j)
H[i][j] = max(H[i][j], H[i][j + 1]);
dp[i][i] = H[i][1];
}
for(int h = 1; h < N; ++h)
for(int i = 1; i + h <= N; ++i) {
int j = i + h;
dp[i][j] = max(H[j][j - i + 1] * (j - i + 1), max(dp[i + 1][j], dp[i][j - 1]));
}
for(int i = 1; i < N; ++i)
sol = max(sol, dp[1][i] + dp[i + 1][N]);
}
void transpose() {
int T[MAX_N][MAX_N];
memset(T, 0, sizeof(T));
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
T[j][i] = A[i][j];
swap(N, M);
memset(A, 0, sizeof(A));
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
A[i][j] = T[i][j];
}
void solve() {
compute();
transpose();
compute();
}
void write() {
ofstream g("bmatrix.out");
g << sol << "\n";
g.close();
}
int main() {
read();
solve();
write();
return 0;
}