Pagini recente » Cod sursa (job #82293) | Cod sursa (job #1587132) | Cod sursa (job #160435) | Cod sursa (job #961795) | Cod sursa (job #819132)
Cod sursa(job #819132)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 100
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
struct point {
int first, second;
};
int n1, n2;
int m[MAXN][MAXN], a[MAXN][MAXN];
int dimCoada;
point coada[MAXN];
void doSums(int sti, int stj, int fni, int fnj) {
memset (a, 0, sizeof(a));
for (int i = sti; i <= fni; ++i)
for (int j = stj; j <= fnj; ++j)
if (m[i][j] == 0)
a[i][j] = a[i - 1][j] + 1;
}
void addElem(point e, int &rez) {
while (dimCoada > 0 && e.first < coada[dimCoada].first) {
int dim = 1;
point aux = coada[dimCoada];
while (coada[dimCoada].first == coada[dimCoada - 1].first) {
--dimCoada;
++dim;
}
if (dimCoada == 1)
dim += coada[dimCoada].second - 1;
rez = max(rez, dim * aux.first);
--dimCoada;
}
coada[++dimCoada] = e;
}
int doDinamicu (int sti, int stj, int fni, int fnj) {
int maxDrept = 0;
doSums (sti, stj, fni, fnj);
for (int i = sti; i <= fni; ++i) {
point aux;
for (int j = stj; j <= fnj; ++j) {
aux.first = a[i][j];
aux.second = j - stj + 1;
addElem(aux, maxDrept);
}
aux.first = -1;
addElem(aux, maxDrept);
--dimCoada;
}
return maxDrept;
}
void read() {
fin >> n1 >> n2;
for (int i = 1; i <= n1; ++i) {
fin.get();
for (int j = 1; j <= n2; ++j) {
char c = fin.get();
m[i][j] = (int)c - '0';
}
}
}
int solve() {
int maxSol = 0;
for (int i = 1; i <= n1; ++i)
maxSol = max (maxSol, doDinamicu (1, 1, i, n2) + doDinamicu (i + 1, 1, n1, n2));
for (int i = 1; i <= n2; ++i)
maxSol = max (maxSol, doDinamicu (1, 1, n1, i) + doDinamicu (1, i + 1, n1, n2));
return maxSol;
}
int main() {
read();
fout << solve();
return 0;
}