Pagini recente » Cod sursa (job #447519) | Cod sursa (job #2771276) | Cod sursa (job #967748) | Cod sursa (job #820128) | Cod sursa (job #816237)
Cod sursa(job #816237)
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 210;
int n, m, smax[N], antS[N], s[N], u, d[N][N], rez, cs[N], cd[N];
char a[N][N], b[N][N];
void calc() {
int i, j, k;
for(i = 1; i<=n; ++i)
for(j = 1; j<=m; ++j)
d[i][j] = (a[i][j] == '1' ? 0 : d[i - 1][j] + 1);
for(i = 1; i <= n; ++i) {
s[0] = 0;
u = 0;
for(j = 1; j<=m; ++j) {
while(u && d[i][s[u]] >= d[i][j])
--u;
s[++u] = j;
cs[j] = s[u - 1] + 1;
}
u = 0;
antS[i] = antS[i - 1];
s[0] = m + 1;
for(j = m; j; --j) {
while(u && d[i][s[u]] >= d[i][j])
--u;
s[++u] = j;
cd[j] = s[u - 1] - 1;
antS[i] = max(antS[i], (cd[j] - cs[j] + 1) * d[i][j]);
//for(k = 1; k<=d[i][j]; ++k)
//rez = max(rez, (cd[j] - cs[j] + 1) * k + antS[i - k]);
}
}
for(i = n; i; --i)
for(j = 1; j<=m; ++j) {
d[n + 1][j] = 0;
d[i][j] = (a[i][j] == '1' ? 0 : d[i + 1][j] + 1);
}
for(i = 1; i <= n; ++i) {
s[0] = 0;
u = 0;
for(j = 1; j<=m; ++j) {
while(u && d[i][s[u]] >= d[i][j])
--u;
s[++u] = j;
cs[j] = s[u - 1] + 1;
}
u = 0;
antS[i] = antS[i - 1];
s[0] = m + 1;
for(j = m; j; --j) {
while(u && d[i][s[u]] >= d[i][j])
--u;
s[++u] = j;
cd[j] = s[u - 1] - 1;
rez = max(rez, antS[i - 1] + (cd[j] - cs[j] + 1) * d[i][j]);
//for(k = 1; k<=d[i][j]; ++k)
//rez = max(rez, (cd[j] - cs[j] + 1) * k + antS[i - k]);
}
}
}
int main() {
int i, j;
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
cin >> n >> m;
cin.get();
for(i = 1; i<=n; ++i)
cin.getline(a[i] + 1, N);
calc();
for(i = 1; i<=max(n, m); ++i)
for(j = 1; j<=max(m, n); ++j)
b[i][j] = a[j][i];
swap(n, m);
for(i = 1; i<=n; ++i)
for(j = 1; j<=m; ++j)
a[i][j] = b[i][j];
calc();
cout << rez;
return 0;
}