Submission #704714

#	Time	Username	Problem	Language	Result	Execution time	Memory
704714		KiriLL1ca	Bomb (IZhO17_bomb)	C++17	20 / 100	1093 ms	56436 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;

inline void solve () {
    int n, m; cin >> n >> m;
    vector <string> a (n);
    for (auto &i : a) cin >> i;
    vector <vector <int>> p (n, vector <int> (m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i) p[i][j] += p[i - 1][j];
            if (j) p[i][j] += p[i][j - 1];
            if (i && j) p[i][j] -= p[i - 1][j - 1];
            p[i][j] += (a[i][j] - '0');
        }
    }

    auto get = [&] (int x, int y, int xx, int yy) {
        int res = p[xx][yy];
        if (x) res -= p[x - 1][yy];
        if (y) res -= p[xx][y - 1];
        if (x && y) res += p[x - 1][y - 1];
        return res;
    };

    int ans = 0;

    {
        int side = 1e9;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int res = 0;
                for (int q = 12; ~q; --q) {
                    res += pw(q);
                    if (j + res - 1 >= m || get(i, j, i, j + res - 1) != res) res -= pw(q);
                }
                if (res) umin(side, res);
                j += res;
            }
        }

        auto bad = [&] (int t) {
            vector <vector <int>> f (n + 1, vector <int> (m + 1));

            for (int i = 0; i + t - 1 < n; ++i) {
                for (int j = 0; j + side - 1 < m; ++j) {
                    if (get(i, j, i + t - 1, j + side - 1) == side * t) {
                        ++f[i][j];
                        --f[i + t][j];
                        --f[i][j + side];
                        ++f[i + t][j + side];
                    }
                }
            }

            for (int i = 0; i <= n; ++i) {
                for (int j = 0; j <= m; ++j) {
                    if (i) f[i][j] += f[i - 1][j];
                    if (j) f[i][j] += f[i][j - 1];
                    if (i && j) f[i][j] -= f[i - 1][j - 1];
                }
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (a[i][j] == '1' && !f[i][j]) return 1;
                }
            }
            return 0;
        };

        int res = 0;
        for (int i = 12; ~i; --i) {
            res += pw(i);
            if (bad(res)) res -= pw(i);
        }
        umax(ans, side * res);
    }

    {

        int side = 1e9;
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n; ++i) {
                int res = 0;
                for (int q = 12; ~q; --q) {
                    res += pw(q);
                    if (i + res - 1 >= n || get(i, j, i + res - 1, j) != res) res -= pw(q);
                }
                if (res) umin(side, res);
                i += res;
            }
        }

        auto bad = [&] (int t) {
            vector <vector <int>> f (n + 1, vector <int> (m + 1));

            for (int i = 0; i + side - 1 < n; ++i) {
                for (int j = 0; j + t - 1 < m; ++j) {
                    if (get(i, j, i + side - 1, j + t - 1) == side * t) {
                        ++f[i][j];
                        --f[i + side][j];
                        --f[i][j + t];
                        ++f[i + side][j + t];
                    }
                }
            }

            for (int i = 0; i <= n; ++i) {
                for (int j = 0; j <= m; ++j) {
                    if (i) f[i][j] += f[i - 1][j];
                    if (j) f[i][j] += f[i][j - 1];
                    if (i && j) f[i][j] -= f[i - 1][j - 1];
                }
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (a[i][j] == '1' && !f[i][j]) return 1;
                }
            }
            return 0;
        };

        int res = 0;
        for (int i = 12; ~i; --i) {
            res += pw(i);
            if (bad(res)) res -= pw(i);
        }
        umax(ans, side * res);
    }
    cout << ans;
}

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: 20 / 100