Submission #1128783

#TimeUsernameProblemLanguageResultExecution timeMemory
1128783farni4kBomb (IZhO17_bomb)C++20
12 / 100
111 ms55508 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2501;
char c[N][N];
int dp[N][N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; cin>>n>>m;
    for (int i = 1; i<=n; i++) {
        for (int j = 1; j<=m; j++) {
            cin>>c[i][j];
            dp[i][j]=0;
            if (c[i][j]=='1') dp[i][j]=1;
        }
    }

    int mxx=1000000,mxy=1000000;
    for (int i = 1; i<=m; i++) {
        int st=-1,end=-1,mxst=-1,mxend=-1;
        for (int j = 1; j<=n; j++) {
            if (c[j][i]=='1') {
                if (st==-1) st=j;
                else if (end==-1 && j==1) {
                    end=j;
                    if ((end-st+1)>(mxend-mxst+1) || (mxst==-1 && mxend==-1)) {
                        mxend=end;
                        mxst=st;
                    }
                }
            } else {
                if (end==-1 && st!=-1) {
                    end=j-1;
                    if ((end-st+1)>(mxend-mxst+1) || (mxst==-1 && mxend==-1)) {
                        mxend=end;
                        mxst=st;
                    }
                }
            }
        }
        if (mxst==-1 && mxend==-1 && st>0 && end>0) {
            mxend=end;
            mxst=st;
        }
        if ((mxend-mxst+1)<mxy && mxst!=-1 && mxend!=-1) mxy=mxend-mxst+1;
    }

    for (int i = 1; i<=n; i++) {
        int st=-1,end=-1,mxst=-1,mxend=-1;
        for (int j = 1; j<=m; j++) {
            if (c[i][j]=='1') {
                if (st==-1) st=j;
                else if (end==-1 && j==1) {
                    end=j;
                    if ((end-st+1)>(mxend-mxst+1) || (mxst==-1 && mxend==-1)) {
                        mxend=end;
                        mxst=st;
                    }
                }
            } else {
                if (end==-1 && st!=-1) {
                    end=j-1;
                    if ((end-st+1)>(mxend-mxst+1) || (mxst==-1 && mxend==-1)) {
                        mxend=end;
                        mxst=st;
                    }
                }
            }
        }
        if (mxst==-1 && mxend==-1 && st>0 && end>0) {
            mxend=end;
            mxst=st;
        }
        // cout<<st<<' '<<end<<'\n';
        if ((mxend-mxst+1)<mxx && mxst!=-1 && mxend!=-1) mxx=mxend-mxst+1;
    }
    
    cout<<mxx*mxy;
}
#Verdict Execution timeMemoryGrader output
Fetching results...