Submission #945057

#	Time	Username	Problem	Language	Result	Execution time	Memory
945057		atom	Bomb (IZhO17_bomb)	C++17	62 / 100	2543 ms	131072 KiB

bomb

#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;
        }
    }

    // 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
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            a[i][j]? lt[i][j] = (lt[i][j - 1] + 1) : 0;

        for (int j = m; j >= 1; --j)
            a[i][j]? rt[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

    int min_h = 1e9; // minimum vertical strip of 1s;
    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;
            }
        }
    }

    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";
}

• Subtask 1: 62 / 100