Pagini recente » Lista lu' Francu | Cod sursa (job #1183461) | Cod sursa (job #106365) | Cod sursa (job #587810) | Cod sursa (job #824722)
Cod sursa(job #824722)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int MAX_N = 300;
bool m[MAX_N][MAX_N];
int N, M, sol;
void read();
void solve();
void find_mat(int rez[]);
void change_direction();
void rotate();
void print();
int main() {
read();
solve();
rotate();
solve();
print();
return 0;
}
void read() {
string line;
fin >> N >> M;
getline(fin, line);
for (int i = 1; i <= N; ++i) {
getline(fin, line);
for (int j = 1; j <= M; ++j) {
m[i][j] = line[j-1] - '0';
}
}
}
void solve() {
int rez1[MAX_N], rez2[MAX_N];
memset(rez1, 0, sizeof(rez1));
memset(rez2, 0, sizeof(rez2));
find_mat(rez1);
change_direction();
find_mat(rez2);
change_direction();
for (int i = 1; i < N; ++i) {
sol = max(sol, rez1[i] + rez2[N-i]);
}
}
struct col {int h, pos;};
void find_mat(int rez[]) {
col st[MAX_N];
int stTop = 0;
int row[MAX_N];
for (int i = 0; i <= M; ++i) row[i] = 0;
for (int i = 1; i <= N; ++i) {
row[M+1] = 0;
for (int j = 1; j <= M + 1; ++j) {
if (m[i][j] == false) {
++row[j];
} else {
row[j] = 0;
}
int p = j;
while (stTop > 0 && row[j] <= st[stTop].h) {
rez[i] = max(rez[i], st[stTop].h * (j - st[stTop].pos));
p = st[stTop].pos;
--stTop;
}
st[++stTop].h = row[j];
st[stTop].pos = p;
}
rez[i] = max(rez[i], rez[i-1]);
}
}
void change_direction() {
for (int i = 1; i <= N / 2; ++i) {
for (int j = 1; j <= M; ++j) {
swap(m[i][j], m[N-i+1][j]);
}
}
}
void rotate() {
bool temp[MAX_N][MAX_N];
memcpy(temp, m, sizeof(m));
for (int i = 1; i <= M; ++i) {
for (int j = 1; j <= N; ++j) {
temp[i][j] = m[j][i];
}
}
memcpy(m, temp, sizeof(temp));
swap(N, M);
}
void print() {
fout << sol;
}