Pagini recente » Cod sursa (job #1048843) | Cod sursa (job #778382) | Cod sursa (job #2160946) | Cod sursa (job #1086152) | Cod sursa (job #3338874)
#include <bits/stdc++.h>
using namespace std;
#define USE_STD_IO 0
#if USE_STD_IO
#define fin cin
#define fout cout
#else
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
#endif
int n, m, i, j, h[202];
int st[202], dr[202];
int top, stiv[202];
bool a[202][202];
char car;
static inline int DAYUM_Skyline(int cst, int cdr) {
memset(st, 0, sizeof(st));
memset(dr, 0, sizeof(dr));
stiv[top = 0] = cst - 1;
for(int j = cst; j <= cdr; j++) {
while(top && h[stiv[top]] >= h[j]) top--;
st[j] = stiv[top];
stiv[++top] = j;
}
stiv[top = 0] = cdr + 1;
for(int j = cdr; j >= cst; j--) {
while(top && h[stiv[top]] >= h[j]) top--;
dr[j] = stiv[top];
stiv[++top] = j;
}
int arie = 0;
for(int j = cst; j <= cdr; j++) {
arie = max(arie, h[j] * (dr[j] - st[j] - 1));
}
/*for(int j = cst; j <= cdr; j++) cout << st[j] << " ";
cout << "\n";
for(int j = cdr; j >= cst; j--) cout << dr[j] << " ";
cout << "\n\n";*/
return arie;
}
static inline int DAYUM_Plaja(int lst, int ldr, int cst, int cdr) {
int arie = 0;
for(int i = lst; i <= ldr; i++) {
for(int j = cst; j <= cdr; j++) h[j] = 0;
for(int ii = i; ii <= ldr; ii++) {
for(int j = cst; j <= cdr; j++) {
if(!a[ii][j]) h[j]++;
else h[j] = 0;
}
arie = max(arie, DAYUM_Skyline(cst, cdr));
}
}
return arie;
}
static inline int DAYUM_SplitMat() {
int arie = 0;
for(int i = 1; i < n; i++) {
arie = max(arie, DAYUM_Plaja(1, i, 1, m) + DAYUM_Plaja(i + 1, n, 1, m));
}
for(int j = 1; j < m; j++) {
arie = max(arie, DAYUM_Plaja(1, n, 1, j) + DAYUM_Plaja(1, n, j + 1, m));
}
return arie;
}
int main() {
if(USE_STD_IO) ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> n >> m;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
fin >> car;
a[i][j] = car - '0';
}
}
fout << DAYUM_SplitMat();
return 0;
}