Cod sursa(job #3185063)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 17 decembrie 2023 19:15:19
Problema BMatrix Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int NMAX = 201;

int a[NMAX][NMAX], dir[NMAX][NMAX];
int lin_sus[NMAX], lin_jos[NMAX], col_st[NMAX], col_dr[NMAX];
int n, m;
void debug( int N, int M){
    for( int l = 1; l <= N; l++ ){
        for( int c = 1; c <= M; c++ )
            out << dir[l][c];
        out << "\n";
    }
    out << "\n";
}
int skyline( deque <int> dq ){
    int x = dq.size(), aria = 0;
    for( int i = 0; i < x; i++ )
        aria = max( aria, dq.front() * (x-i) ), dq.pop_front();
    return aria;
}
void bmatrix( int N, int M, int mat[NMAX][NMAX], int linie_sus[NMAX] ){
    int up[NMAX];
    for( int i = 1; i <= M; i++ )
        up[i] = 0;
    for( int l = 1; l <= N; l++ ){
        int aria = 0;
        deque <int> dq;
        for( int c = 1; c <= M; c++ ){
            if( mat[l][c] == 0 ){
                up[c]++;
                aria = max( aria, up[c] );
                int lenght = 1;
                while( dq.size() && up[c] < dq.back() ){
                    dq.pop_back();
                    lenght++;
                }
                aria = max( aria, lenght * up[c]);
                dq.push_back(up[c]);
                aria = max( aria, skyline(dq) );
            }
            else{
                up[c] = 0;
                dq.clear();
            }
        }
        linie_sus[l] = max(aria, linie_sus[l-1]);
    }
}
int main()
{
    in >> n >> m;
    for( int l = 1; l <= n; l++ ){
        char ch;
        for( int c = 1; c <= m; c++ ){
            in >> ch;
            a[l][c] = ch - '0';
        }
    }
    for( int l = 1; l <= n; l++ )
        for( int c = 1; c <= m; c++ )
            dir[l][c] = a[l][c];
//    debug(n, m);
    bmatrix(n, m, dir, lin_sus);

    for( int l = 1; l <= n/2; l++ )
        for( int c = 1; c <= m; c++ ){
            dir[l][c] = a[n-l+1][c];
            dir[n-l+1][c] = a[l][c];
        }
//    debug(n, m);
    bmatrix(n, m, dir, lin_jos);

    for( int l = 1; l <= m; l++ )
        for( int c = 1; c <= n; c++ )
            dir[l][c] = a[n-c+1][l];
//    debug(m, n);
    bmatrix(m, n, dir, col_dr);

    for( int l = 1; l <= m; l++ )
        for( int c = 1; c <= n; c++ )
            dir[l][c] = a[c][m-l+1];
    bmatrix(m, n, dir, col_st);


    int rez = 0;
    for( int i = 1; i <= n; i++ ){
        if( 2*i != n+1)
            rez = max( rez, lin_sus[i] + lin_jos[n-i] );
        else
            rez = max( rez, lin_sus[i+1] + lin_jos[i]);
//        out << lin_sus[i] << " " << lin_jos[i] << "\n";
    }
//    out << "\n";
    for( int i = 1; i <= m; i++ ){
        if( 2 * i != m+1 )
            rez = max( rez, col_dr[i] + col_st[m-i]);
        else
            rez = max( rez, col_dr[i+1] + col_st[i]);
//        out << col_dr[i] << " " << col_st[i] << "\n";
    }
    out << rez;
    return 0;
}