Pagini recente » Cod sursa (job #2592380) | Cod sursa (job #1754482) | Cod sursa (job #2197386) | Cod sursa (job #589879) | Cod sursa (job #824548)
Cod sursa(job #824548)
#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 = 201;
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();
void debug();
int main() {
read();
debug();
solve();
rotate();
solve();
print();
return 0;
}
void debug() {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
cerr << m[i][j] << ' ';
}
cerr << endl;
}
cerr << endl;
}
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';
}
cerr << endl;
}
}
void solve() {
int rez1[MAX_N], rez2[MAX_N];
memset(rez1, 0, sizeof(rez1));
memset(rez2, 0, sizeof(rez2));
debug();
find_mat(rez1);
change_direction();
debug();
find_mat(rez2);
change_direction();
for (int i = 1; i < N; ++i) {
sol = max(sol, rez1[i] + rez2[N-i]);
cerr << rez1[i] << ' ' << rez2[N-i] << endl;
}
cerr << sol << endl;
}
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) {
for (int j = 1; j <= M; ++j) {
if (m[i][j] == false) {
++row[j];
} else {
row[j] = 0;
stTop = 0;
}
int p = j;
while (stTop > 0 && row[j] < st[stTop].h) {
p = st[stTop].pos;
--stTop;
}
if (stTop > 0 && st[stTop].h == row[j]) p = st[stTop].pos;
st[++stTop].h = row[j];
st[stTop].pos = p;
rez[i] = max(rez[i], st[stTop].h * (j - st[stTop].pos + 1));
cerr << st[stTop].h << ' ' << st[stTop].pos << endl;
}
while (stTop > 0) {
rez[i] = max(rez[i], st[stTop].h * (M - st[stTop].pos + 1));
--stTop;
}
rez[i] = max(rez[i], rez[i-1]);
cerr << rez[i] << endl;
}
}
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;
}