Submission #1365975

#TimeUsernameProblemLanguageResultExecution timeMemory
1365975nguyenkhangninh99Bomb (IZhO17_bomb)C++20
100 / 100
196 ms66632 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e3 + 5;
int top[maxn][maxn], bot[maxn][maxn], at[maxn], w[maxn];
char a[maxn][maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cin >> a[i][j];
    }

    int mw = 1e9, mh = 1e9;
    for(int j = 1; j <= m; j++){
        for(int i = 1; i <= n; i++){
            if(a[i][j] == '0') continue;
            top[i][j] = top[i - 1][j] + 1;
        }
        for(int i = n; i >= 1; i--){
            if(a[i][j] == '0') continue;
            bot[i][j] = bot[i + 1][j] + 1;
        }
        for(int i = 1; i <= n; i++){
            if(a[i][j] == '1') at[i]++;
            else{
                if(at[i]) mw = min(mw, at[i]);
                at[i] = 0;
            }
        }
    }
    for(int i = 1; i <= n; i++) if(at[i]) mw = min(mw, at[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == '1') mh = min(mh, top[i][j] + bot[i][j] - 1);
        }
    }
    for(int i = 0; i <= mw; i++) w[i] = mh;
    
    for(int i = 1; i <= n; i++){
        int ln = 0, ma = 1e9, mb = 1e9;
        for(int j = 1; j <= m; j++){
            if(a[i][j] == '1'){
                ma = min(ma, top[i][j]),
                mb = min(mb, bot[i][j]);
                ln++;
                w[ln] = min(w[ln], ma + mb - 1);
            }else ln = 0, ma = 1e9, mb = 1e9;
        }
        ln = 0, ma = 1e9, mb = 1e9;
        for(int j = m; j >= 1; j--){
            if(a[i][j] == '1'){
                ma = min(ma, top[i][j]),
                mb = min(mb, bot[i][j]);
                ln++;
                w[ln] = min(w[ln], ma + mb - 1);
            }else ln = 0, ma = 1e9, mb = 1e9;
        }
    }
    int ans = 0;
    for(int i = 0; i <= mw; i++) ans = max(ans, i * w[i]);
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...