Submission #1010985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010985		LucaIlie	Bomb (IZhO17_bomb)	C++17	21 / 100	1103 ms	77392 KiB

bomb

#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);
    }

    int maxArea = 0;
    for ( int w = 1; w <= m; w++ ) {
        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 = 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] = n;
            }

            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;
}

• Subtask 1: 21 / 100