Submission #706360

#	Time	Username	Problem	Language	Result	Execution time	Memory
706360		nifeshe	Bomb (IZhO17_bomb)	C++17	76 / 100	689 ms	56336 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define vec vector
#define pw(x) (1ll << x)
 
using namespace std;
using namespace __gnu_pbds;
 
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int inf = 1e9 + 17;
 
inline void solve () {
    int n, m; cin >> n >> m;
    vec <string> a (n);
    for (auto &i : a) cin >> i;
 
    vec <int> mx (m + 2, inf);
 
    for (int iter = 0; iter < 2; ++iter) {
        vec <vec <int>> p (n, vec <int> (m)), s (n, vec <int> (m));
        for (int j = 0; j < m; ++j) {
            p[0][j] = (a[0][j] == '1');
            for (int i = 1; i < n; ++i) {
                if (a[i][j] == '1') p[i][j] = p[i - 1][j] + 1;
            }
 
            s[n - 1][j] = (a[n - 1][j] == '1');
            for (int i = n - 2; ~i; --i) {
                if (a[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
            }
 
            for (int i = 0; i < n; ++i) if (a[i][j] == '1') umin(mx[1], p[i][j] + s[i][j] - 1);
        }
 
        for (int i = 0; i < n; ++i) {
            for (int l = 0, r = 0; r < m; ) {
                while (r < m && a[i][r] == '1') ++r;
                if (l == r) {
                    ++l, ++r;
                    continue;
                }
 
                int mn_down = inf, mn_up = inf;
                for (int q = l; q < r; ++q) {
                    umin(mn_up, p[i][q]);
                    umin(mn_down, s[i][q]);
                    umin(mx[q - l + 1], mn_down + mn_up - 1);
                }
                umin(mx[r - l + 1], 0);
 
                l = r;
            }
        }
 
        for (auto &i : a) reverse(all(i));
    }
 
    int ans = 0;
    bool ok = 0;
    for (int i = 1; i <= m; ++i) {
        umin(mx[i], mx[i - 1]);
        if (i > 1 && mx[i] != mx[i - 1] && mx[i] > 0) ok = 1;
        umax(ans, mx[i] * i);
    }
    assert(ok);
    cout << ans << endl;
}
 
signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif// LOCAL
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 76 / 100