Submission #945096

#TimeUsernameProblemLanguageResultExecution timeMemory
945096atomBomb (IZhO17_bomb)C++17
98 / 100
2683 ms131072 KiB
    #include "bits/stdc++.h"
    // @JASPER'S BOILERPLATE
    using namespace std;
    using ll = long long;
     
    #ifdef JASPER
    #include "debug.h"
    #else
    #define debug(...) 166
    #endif
     
    signed main() {
        cin.tie(0) -> sync_with_stdio(0);
        #ifdef JASPER
            freopen("in1", "r", stdin);
        #endif
     
        int n, m;
        cin >> n >> m;
        vector <vector <int>> a(n + 5, vector <int> (m + 5, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                char x; cin >> x;
                a[i][j] = x - '0';
            }
        }
     
        // for (int i = 1; i <= n; ++i) 
        //     for (int j = 1; j <= m; ++j)
        //         cout << a[i][j] << " \n"[j == m]; 
     
        //sub1: shortest consecutive 1ss
        if (n == 1 || m == 1) {
            if (n == 1) {
                int ans = 1e9;
                for (int i = 1; i <= m; ++i) {
                    if (a[1][i] == 0) continue;
                    int cur = 0;
                    while (i <= m && a[1][i]) { 
                        ++cur;
                        ++i;
                    }
                    ans = min(ans, cur);
                }
                cout << ans << "\n";
                return 0;
            }
            if (m == 1) {
                int ans = 1e9;
                for (int i = 1; i <= n; ++i) {
                    if (a[i][1] == 0) continue;
                    int cur = 0;
                    while (i <= n && a[i][1]) { 
                        ++cur;
                        ++i;
                    }
                    ans = min(ans, cur);
                }
                cout << ans << "\n";
                return 0;
            }
        }
     
        // sub3
        // if (n <= 450 && m <= 450) {
        //     vector <vector <int>> prf(n + 5, vector <int> (m + 5, 0));
        //     int earth = 0;
        //     for (int i = 1; i <= n; ++i) {
        //         for (int j = 1; j <= m; ++j) {
        //             earth += (a[i][j] == 0);
        //             prf[i][j] = prf[i][j - 1] + prf[i - 1][j] - prf[i - 1][j - 1] + a[i][j];
        //         }
        //     }
     
        //     int ans = 0;
        //     for (int x = 1; x <= n; ++x) {
        //         for (int y = 1; y <= m; ++y) {
        //             if (x * y <= ans) continue;
     
        //             // prf(l)++, prf(r + 1)--;
        //             vector <vector <int>> dmg(n + 2, vector <int> (m + 2, 0));
     
        //             for (int i = 1; i + x - 1 <= n; ++i) {
        //                 for (int j = 1; j + y - 1 <= m; ++j) {
        //                     int I = i + x - 1, J = j + y - 1;
        //                     if (prf[I][J] + prf[i - 1][j - 1] - prf[I][j - 1] - prf[i - 1][J] == x * y) {
        //                         dmg[i][j] += 1;
        //                         dmg[I + 1][j] -= 1;
        //                         dmg[i][J + 1] -= 1;
        //                         dmg[I + 1][J + 1] += 1;
        //                     }
        //                 }
        //             }
     
        //             for (int i = 1; i <= n; ++i)
        //                 for (int j = 1; j <= m; ++j)
        //                     dmg[i][j] += dmg[i - 1][j] + dmg[i][j - 1] - dmg[i - 1][j - 1];
     
        //             bool valid = 1;
        //             for (int i = 1; i <= n; ++i) {
        //                 for (int j = 1; j <= m; ++j) {
        //                     if (a[i][j] && !dmg[i][j])
        //                         valid = 0;
        //                 }
        //             }
        //             if (valid) ans = max(ans, x * y);
        //         }
        //     }
     
        //     cout << ans << "\n";
        //     return 0;
        // }
        
     
     
        // two pointer to optimize
        vector <vector <int>> lt(n + 5, vector <int> (m + 5, 0)), rt(n + 5, vector <int> (m + 5, 0));
        vector <int> w(n + 5, 1e9); // ans(i) : W when H = i
        int min_h = 1e9;// minimum vertical strip of 1s;
     
        for (int _i = 0; _i <= 1; _i++) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j)
                    lt[i][j] = a[i][j]? (lt[i][j - 1] + 1) : 0;
     
                for (int j = m; j >= 1; --j)
                    rt[i][j] = a[i][j]? (rt[i][j + 1] + 1) : 0;
     
                for (int j = 1; j <= m; ++j)
                    if (a[i][j]) w[1] = min(w[1], rt[i][j] + lt[i][j] - 1);
            }
            // find feasible height
            for (int j = 1; j <= m; ++j) {
                int k = 0; // length of consecutive 1s of current column
                int l = 1e9, r = 1e9;
                for (int i = 1; i <= n; ++i) {
                    if (a[i][j]) {
                        ++k;
                        l = min(l, lt[i][j]);
                        r = min(r, rt[i][j]);
                        w[k] = min(w[k], r + l - 1);
                    }
                    else {
                        if (k) min_h = min(min_h, k);
                        l = r = 1e9;
                        k = 0;
                    }
                }
            }
     
            for (int i = 1; i <= n / 2; ++i) {
                for (int j = 1; j <= m; ++j)
                    swap(a[i][j], a[n - i + 1][j]);
            }
     
        }
     
        int ans = 0;
        for (int h = 1; h <= min_h; ++h) {
            w[h + 1] = min(w[h + 1], w[h]); // width is bounded by the minimum horizontal strip
            ans = max(ans, w[h] * h);
        }
     
        cout << ans << "\n";
    }
#Verdict Execution timeMemoryGrader output
Fetching results...