Submission #1279887

#TimeUsernameProblemLanguageResultExecution timeMemory
1279887dostsBomb (IZhO17_bomb)C++20
24 / 100
157 ms105012 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;

void solve() {
    int n,m;
    cin >> n >> m;
    vector<string> grid(n);
    for (auto& row : grid) cin >> row;
    int r[n][m]{},d[n][m]{};
    for (int i = 0;i<n;i++) {
        for (int j = m-1;j>=0;j--) {
            if (grid[i][j] == '0') {
                r[i][j] = inf;
                continue;
            }
            if (j!=m-1) r[i][j] = (r[i][j+1]<inf)*r[i][j+1]+1;
            else r[i][j] = 1;
        }
    }
    for (int j = 0;j<m;j++) {
        for (int i = n-1;i>=0;i--) {
            if (grid[i][j] == '0') {
                d[i][j] = inf;
                continue;
            }
            if (i!=n-1) d[i][j] = (d[i+1][j]<inf)*d[i+1][j]+1;
            else d[i][j] = 1;
        }
    }
    int mn1 = n,mn2 = m;
    for (int i = 0;i<n;i++) {
        for (int j = 0;j<m;j++) {
            if (grid[i][j] == '0') continue;
            if (!j || grid[i][j-1] == '0') mn2 = min(mn2,r[i][j]);
            if (!i || grid[i-1][j] == '0') mn1 = min(mn1,d[i][j]);
        }
    }
    cout << mn1*mn2 << endl;
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...