제출 #706320

#제출 시각아이디문제언어결과실행 시간메모리
706320KiriLL1caBomb (IZhO17_bomb)C++17
32 / 100
257 ms57228 KiB
#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 + 1, inf);

    vec <vec <int>> p (n, vec <int> (m)), s (n, vec <int> (m));
    for (int j = 0; j < n; ++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) {
        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;
        }
    }

    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        umin(mx[i], mx[i - 1]);
        umax(ans, mx[i] * i);
    }
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...