Pagini recente » Cod sursa (job #1417062) | Cod sursa (job #2482504) | Cod sursa (job #1769584) | Cod sursa (job #105081) | Cod sursa (job #1840357)
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;
int a[255][255];
int aux[255][255];
char s[255];
void rotate_matrix(int &n, int &m) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
aux[j][n - i + 1] = a[i][j];
}
}
swap(n, m);
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
a[i][j] = aux[i][j];
}
}
}
void dump(int matrix[255][255], int n, int m) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
cout << matrix[i][j] << " ";
}
cout << "\n";
}
}
int up[255], down[255];
int c[255][255];
int l[255], r[255];
int st[255];
int soldiers_row(int a[255], int n) {
///get_left
int k = 0; st[0] = 0;
for (int i = 1; i <= n; ++ i) {
while (k > 0 && a[st[k]] >= a[i]) {
-- k;
}
l[i] = st[k];
st[++ k] = i;
}
///get_right
k = 0; st[0] = n + 1;
for (int i = n; i >= 1; -- i) {
while (k > 0 && a[st[k]] >= a[i]) {
-- k;
}
r[i] = st[k];
st[++ k] = i;
}
int answer = 0;
for (int i = 1; i <= n; ++ i) {
answer = max(answer, a[i] * (r[i] - l[i] - 1));
}
return answer;
}
void get_up_array(int n, int m, int up[255]) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (a[i][j] == 0) {
c[i][j] = c[i - 1][j] + 1;
} else {
c[i][j] = 0;
}
}
}
for (int i = 1; i <= n; ++ i) {
up[i] = max(up[i - 1], soldiers_row(c[i], m));
}
}
int solve(int n, int m) {
get_up_array(n, m, up);
rotate_matrix(n, m);
rotate_matrix(n, m);
get_up_array(n, m, down);
reverse(down + 1, down + n + 1);
int answer = 0;
for (int i = 1; i < n; ++ i) {
answer = max(answer, up[i] + down[i + 1]);
}
return answer;
}
int main() {
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++ i) {
cin >> s;
for (int j = 1; j <= m; ++ j) {
a[i][j] = s[j - 1] - '0';
}
}
int answer = solve(n, m);
rotate_matrix(n, m);
///dump(a, n, m);
answer = max(answer, solve(n, m));
cout << answer << "\n";
return 0;
}