Pagini recente » Cod sursa (job #1481652) | Cod sursa (job #1552920) | Cod sursa (job #3297564) | Cod sursa (job #3273945) | Cod sursa (job #3327427)
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
FILE* fin;
FILE* fout;
const int MAX_M = 200;
const int MAX_N = 200;
struct Seq {
int len, val;
};
int m, n;
char mat[MAX_M][MAX_N], new_mat[MAX_M][MAX_N];
int max_zeros[MAX_M];
int a[MAX_N];
Seq stiva[MAX_N];
int skyline() {
int sp = 0;
int ret = 0;
for(int i = 0; i < n; i++) {
int sum = 0;
while(sp > 0 && a[i] <= stiva[sp - 1].val) {
sum += stiva[sp - 1].len;
if(stiva[sp - 1].val * sum > ret) {
ret = stiva[sp - 1].val * sum;
}
sp--;
}
stiva[sp++] = {sum + 1, a[i]};
}
int sum = 0;
for(; sp > 0; sp--) {
sum += stiva[sp - 1].len;
if(stiva[sp - 1].val * sum > ret) {
ret = stiva[sp - 1].val * sum;
}
}
return ret;
}
int solve() {
for(int c = 0; c < n; c++) {
a[c] = 0;
}
for(int r = 0; r < m; r++) {
for(int c = 0; c < n; c++) {
if(mat[r][c] == 1) {
a[c] = 0;
} else {
a[c]++;
}
}
max_zeros[r] = skyline();
}
for(int c = 0; c < n; c++) {
a[c] = 0;
}
int ret = 0;
for(int r = m - 1; r > 0; r--) {
for(int c = 0; c < n; c++) {
if(mat[r][c] == 1) {
a[c] = 0;
} else {
a[c]++;
}
}
ret = std::max(ret, skyline() + max_zeros[r - 1]);
}
return ret;
}
char next_char() {
char ch;
while(isspace(ch = fgetc(fin)));
return ch;
}
int main() {
fin = fopen("bmatrix.in", "r");
fout = fopen("bmatrix.out", "w");
fscanf(fin, "%d%d", &m, &n);
for(int r = 0; r < m; r++) {
for(int c = 0; c < n; c++) {
mat[r][c] = (next_char() - '0');
}
}
int ans1 = solve();
for(int r = 0; r < m; r++) {
for(int c = 0; c < n; c++) {
new_mat[c][r] = mat[r][c];
}
}
std::swap(m, n);
for(int r = 0; r < m; r++) {
for(int c = 0; c < n; c++) {
mat[r][c] = new_mat[r][c];
}
}
int ans2 = solve();
fprintf(fout, "%d\n", std::max(ans1, ans2));
fclose(fin);
fclose(fout);
return 0;
}