Submission #705999

#TimeUsernameProblemLanguageResultExecution timeMemory
705999KiriLL1caBomb (IZhO17_bomb)C++17
30 / 100
1101 ms58336 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 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) {
        int res = 0;
        for (int j = 9; ~j; --j) {
            res += pw(j);
            if (res > m || bad(i, res, n, m)) res -= pw(j);
        }
        umax(ans, i * res);
    }
    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...