Submission #1011302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011302		LucaIlie	Bomb (IZhO17_bomb)	C++17	100 / 100	284 ms	74068 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 maxWidth = m;
    for ( int i = 0; i <= m; i++ )
        maxHeight[i] = n;
    for ( int l = 1; l <= n; l++ ) {
        int cons1 = 0, hup = n, hdown = n;
        for ( int c = 1; c <= m; c++ ) {
            if ( mat[l][c] ) {
                cons1++;
                hup = min( hup, up[l][c] );
                hdown = min( hdown, down[l][c] );
                maxHeight[cons1] = min( maxHeight[cons1], hup + hdown - 1 );
                maxHeight[1] = min( maxHeight[1], up[l][c] + down[l][c] - 1 );
            } else {
                if ( cons1 > 0 )
                    maxWidth = min( maxWidth, cons1 );
                cons1 = 0, hup = n, hdown = n;
            }
        }
        if ( cons1 > 0 )
            maxWidth = min( maxWidth, cons1 );
    }
    for ( int l = 1; l <= n; l++ ) {
        int cons1 = 0, hup = n, hdown = n;
        for ( int c = m; c >= 1; c-- ) {
            if ( mat[l][c] ) {
                cons1++;
                hup = min( hup, up[l][c] );
                hdown = min( hdown, down[l][c] );
                maxHeight[cons1] = min( maxHeight[cons1], hup + hdown - 1 );
            } else
                cons1 = 0, hup = n, hdown = n;
        }
    }

    int maxArea = 0;
    for ( int i = 1; i <= maxWidth; i++ ) {
        maxHeight[i] = min( maxHeight[i], maxHeight[i - 1] );
        maxArea = max( maxArea, maxHeight[i] * i );
    }
    cout << maxArea;

    return 0;
}

• Subtask 1: 100 / 100