Submission #705995

#	Time	Username	Problem	Language	Result	Execution time	Memory
705995		KiriLL1ca	Bomb (IZhO17_bomb)	C++17	30 / 100	1084 ms	62660 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 N = 2505;

string a[N];
int p[N][N];

inline int 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;
}

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


inline void solve () {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];

    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');
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!bad(i, j, n, m)) umax(ans, i * j);
        }
    }
    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: 30 / 100