# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1010978 | LucaIlie | Bomb (IZhO17_bomb) | C++17 | 1104 ms | 80212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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();
while ( !dq.empty() && hdown[c] + hup[c] >= hdown[dq.back()] + hup[dq.back()] )
dq.pop_back();
dq.push_back( c );
maxHeight[c] = hdown[dq.front()] + hup[dq.front()];
}
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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |