Pagini recente » Cod sursa (job #192283) | Cod sursa (job #1776176) | Cod sursa (job #2304313) | Cod sursa (job #2940466) | Cod sursa (job #2460840)
#include <bits/stdc++.h>
const int MV = 200 ;
FILE *in = fopen("bmatrix.in", "r"), *out = fopen("bmatrix.out", "w") ;
int a[MV + 5][MV + 5], b[MV + 5][MV + 5] ;
int sp[MV + 5], sus[MV + 5], st[MV + 5], l[MV + 5], r[MV + 5] ;
int sky_line(int h[], int m) {
int top(0), j ;
st[top] = 0 ;
for (j = 1 ; j <= m ; ++ j) {
while (top > 0 && h[j] <= h[st[top]])
top -- ;
l[j] = st[top] ;
st[++ top] = j ;
}
top = 0 ;
st[top] = m + 1 ;
for (j = m ; j >= 1 ; -- j) {
while (top > 0 && h[j] <= h[st[top]])
top -- ;
r[j] = st[top] ;
st[++ top] = j ;
}
int ans(0) ;
for (j = 1 ; j <= m ; ++j)
ans = std::max(ans, sp[j] * (r[j] - l[j] - 1)) ;
return ans ;
}
int solve(int x[MV + 5][MV + 5], int n, int m) {
int i, j ;
for (j = 1 ; j <= m ; ++j)
sp[j] = 0 ;
for (i = 1 ; i <= n ; ++i) {
for (j = 1 ; j <= m ; ++j)
if (x[i][j] == 0) {
sp[j]++ ;
} else sp[j] = 0 ;
sus[i] = std::max(sus[i - 1], sky_line(sp, m)) ;
}
int ans = 0 ;
for (j = 1 ; j <= m ; ++j)
sp[j] = 0 ;
int aux = 0 ;
for (i = n ; i >= 1 ; --i) {
for (j = 1 ; j <= m ; ++j)
if (x[i][j] == 0) {
sp[j]++ ;
} else sp[j] = 0 ;
aux = std::max(aux, sky_line(sp, m)) ;
ans = std::max(ans, aux + sus[i - 1]) ;
}
return ans ;
}
int main() {
int n, m ;
fscanf(in, "%d%d", &n, &m) ;
for (int i = 1 ; i <= n ; ++i)
for (int j = 1 ; j <= m ; ++j) {
fscanf(in, "%1d", &a[i][j]) ;
b[m - j + 1][i] = a[i][j] ;
}
fprintf(out, "%d", std::max(solve(a, n, m), solve(b, m, n))) ;
}