Cod sursa(job #2460840)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 24 septembrie 2019 16:16:31
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#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))) ;
}