Submission #706368

#	Time	Username	Problem	Language	Result	Execution time	Memory
706368		nifeshe	Bomb (IZhO17_bomb)	C++17	39 / 100	1094 ms	84196 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
//#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 3e3 + 1;
const int LG = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int n, m;
int pref[MAX][MAX];
int a[MAX][MAX];

int get(int x1, int y1, int x2, int y2) {
    int ans = pref[x2][y2] - (x1? pref[x1 - 1][y2] : 0) - (y1? pref[x2][y1 - 1] : 0) + (x1 && y1? pref[x1 - 1][y1 - 1] : 0);
    return ans;
}

bool bad (int s, int t) {
    vector <vector <int>> f (n + 1, vector <int> (m + 1));
    for (int i = 0; i + s - 1 < n; ++i) {
        for (int j = 0; j + t - 1 < m; ++j) {
            if (!get(i, j, i + s - 1, j + t - 1)) {
                ++f[i][j];
                --f[i + s][j];
                --f[i][j + t];
                ++f[i + s][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] && !f[i][j]) return 1;
        }
    }
    return 0;
}

void solve() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char c;
            cin >> c;
            a[i][j] = c - '0';
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            pref[i][j] = a[i][j] ^ 1;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (i) pref[i][j] += pref[i - 1][j];
            if (j) pref[i][j] += pref[i][j - 1];
            if (i && j) pref[i][j] -= pref[i - 1][j - 1];
        }
    }
    int l = 1, r = min(m, n);
    int x = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(!bad(mid, mid)) {
            l = mid + 1;
            x = mid;
        }
        else r = mid - 1;
    }
    ll ans = 0;
    int lst;
    l = x, r = n;
    lst = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(!bad(mid, x)) {
            l = mid + 1;
            lst = mid;
        }
        else r = mid - 1;
    }
    umax(ans, 1LL * x * lst);
    l = x, r = m;
    lst = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(!bad(x, mid)) {
            l = mid + 1;
            lst = mid;
        }
        else r = mid - 1;
    }
    umax(ans, 1LL * x * lst);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bomb.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

• Subtask 1: 39 / 100