Submission #947393

#	Time	Username	Problem	Language	Result	Execution time	Memory
947393		Pring	Bomb (IZhO17_bomb)	C++17	41 / 100	1092 ms	62468 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 2505;
int n, m;
string s[MXN];

struct P {
    int n, m, a[MXN][MXN];

    void init(int _n, int _m) {
        n = _n;
        m = _m;
        FOR(i, 0, n + 1) FOR(j, 0, m + 1) a[i][j] = 0;
    }

    void BUILD() {
        FOR(i, 1, n + 1) FOR(j, 1, m + 1) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }
    
    int get(int l, int r, int u, int d) {
        return a[r][d] - a[l][d] - a[r][u] + a[l][u];
    }
};

P fld, R;

void MAKE_P() {
    fld.init(n, m);
    FOR(i, 0, n) FOR(j, 0, m) {
        fld.a[i + 1][j + 1] = (s[i][j] - '0');
    }
    fld.BUILD();
}

bool AC(int h, int w) {
    R.init(n + 1, m + 1);
    FOR(i, 0, n - h + 1) FOR(j, 0, m - w + 1) {
        if (fld.get(i, i + h, j, j + w) == h * w) {
            // debug(i, j);
            R.a[i + 1][j + 1]++;
            R.a[i + h + 1][j + 1]--;
            R.a[i + 1][j + w + 1]--;
            R.a[i + h + 1][j + w + 1]++;
        }
    }
    // FOR(i, 0, n + 1) {
    //     FOR(j, 0, m + 1) cout << R.a[i][j] << ' ';
    //     cout << '\n';
    // }
    // cout << endl;
    R.BUILD();
    // FOR(i, 0, n + 1) {
    //     FOR(j, 0, m + 1) cout << R.a[i][j] << ' ';
    //     cout << '\n';
    // }
    // cout << endl;
    int sum = 0;
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        sum += (R.a[i][j] != 0);
    }
    // debug(h, w, sum == fld.a[n][m]);
    return (sum == fld.a[n][m]);
}

int solve() {
    int w = m, ans = 0;
    FOR(h, 1, n + 1) {
        while (w && !AC(h, w)) w--;
        if (w == 0) return ans;
        ans = max(ans, h * w);
    }
    return ans;
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> s[i];
    MAKE_P();
    cout << solve() << '\n';
    // AC(1, 1);
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

• Subtask 1: 41 / 100