Submission #1011016

#TimeUsernameProblemLanguageResultExecution timeMemory
1011016LucaIlieBomb (IZhO17_bomb)C++17
35 / 100
1104 ms79508 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2500;
int mat[MAX_N + 2][MAX_N + 2], up[MAX_N + 2][MAX_N + 2], down[MAX_N + 2][MAX_N + 2], hup[MAX_N + 2], hdown[MAX_N + 2], maxHeight[MAX_N + 2];

int main() {
    int n, m;

    cin >> n >> m;
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            char ch;
            cin >> ch;
            mat[l][c] = ch - '0';
        }
    }

    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ )
            up[l][c] = (mat[l][c] ? up[l - 1][c] + 1 : 0);
    }
    for ( int l = n; l >= 1; l-- ) {
        for ( int c = 1; c <= m; c++ )
            down[l][c] = (mat[l][c] ? down[l + 1][c] + 1 : 0);
    }

    vector<int> withds;
    for ( int i = 1; i <= 30 && i <= m; i++ )
        withds.push_back( i );
    for ( int i = 100; i <= m - 50; i += 300 )
        withds.push_back( m );
    if ( m > 30 ) {
        for ( int i = m - 29; i <= m; i++ )
            withds.push_back( i );
    }

    int maxArea = 0;
    for ( int w: withds ) {
        int h = n;
        for ( int l = 0; l <= n; l++ ) {
            //printf( "LINE %d:\n", l );
            deque<int> dq;
            for ( int c = 1; c <= m; c++ ) {
                if ( !dq.empty() && dq.front() <= c - w )
                    dq.pop_front();
                while ( !dq.empty() && up[l][c] <= up[l][dq.back()] )
                    dq.pop_back();
                dq.push_back( c );
                hup[c] = up[l][dq.front()];
            }
            while ( !dq.empty() )
                dq.pop_back();

            for ( int c = 1; c <= m; c++ ) {
                if ( !dq.empty() && dq.front() <= c - w )
                    dq.pop_front();
                while ( !dq.empty() && down[l + 1][c] <= down[l + 1][dq.back()] )
                    dq.pop_back();
                dq.push_back( c );
                hdown[c] = down[l + 1][dq.front()];
            }
            while ( !dq.empty() )
                dq.pop_back();

            /*for ( int c = 1; c <= m; c++ )
                printf( "%d ", hup[c] );
            printf( "\n" );
            for ( int c = 1; c <= m; c++ )
                printf( "%d ", hdown[c] );
            printf( "\n" );*/

            for ( int c = 1; c <= m; c++ ) {
                if ( hup[c] == 0 )
                    hdown[c] = 0;
            }
            for ( int c = m; c >= 1; c-- ) {
                if ( !dq.empty() && dq.front() >= c + w )
                    dq.pop_front();
                if ( c >= w ) {
                    while ( !dq.empty() && hdown[c] + hup[c] >= hdown[dq.back()] + hup[dq.back()] )
                        dq.pop_back();
                    dq.push_back( c );
                }
                if ( !dq.empty() )
                    maxHeight[c] = hdown[dq.front()] + hup[dq.front()];
                else
                    maxHeight[c] = 0;
            }

            for ( int c = 1; c <= m; c++ ) {
                if ( mat[l][c] )
                    h = min( h, maxHeight[c] );
                //printf( "%d ", mat[l][c] ? maxHeight[c] : 9 );
            }
            //printf( "\n" );
        }

        //printf( "\n\n\n\nBA AVEM W SI H!!!!!!!!!!! %d %d\n\n\n", w, h );

        maxArea = max( maxArea, w * h );
    }

    cout << maxArea;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...