제출 #942714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942714		atom	Bomb (IZhO17_bomb)	C++17	30 / 100	391 ms	31324 KiB

bomb

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    vector <vector <int>> a(n + 5, vector <int> (m + 5, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char x; cin >> x;
            a[i][j] = x - '0';
        }
    }

    // for (int i = 1; i <= n; ++i) 
    //     for (int j = 1; j <= m; ++j)
    //         cout << a[i][j] << " \n"[j == m]; 

    //sub1: shortest consecutive 1ss
    if (n == 1 || m == 1) {
        if (n == 1) {
            int ans = 1e9;
            for (int i = 1; i <= m; ++i) {
                if (a[1][i] == 0) continue;
                int cur = 0;
                while (i <= m && a[1][i]) { 
                    ++cur;
                    ++i;
                }
                ans = min(ans, cur);
            }
            cout << ans << "\n";
            return 0;
        }
        if (m == 1) {
            int ans = 1e9;
            for (int i = 1; i <= n; ++i) {
                if (a[i][1] == 0) continue;
                int cur = 0;
                while (i <= n && a[i][1]) { 
                    ++cur;
                    ++i;
                }
                ans = min(ans, cur);
            }
            cout << ans << "\n";
            return 0;
        }
    }

    // sub3
    if (n <= 100 && m <= 100) {
        vector <vector <int>> prf(n + 5, vector <int> (m + 5, 0));
        int earth = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                earth += (a[i][j] == 0);
                prf[i][j] = prf[i][j - 1] + prf[i - 1][j] - prf[i - 1][j - 1] + a[i][j];
            }
        }

        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= m; ++y) {
                if (x * y <= ans) continue;

                // prf(l)++, prf(r + 1)--;
                vector <vector <int>> dmg(n + 2, vector <int> (m + 2, 0));

                for (int i = 1; i + x - 1 <= n; ++i) {
                    for (int j = 1; j + y - 1 <= m; ++j) {
                        int I = i + x - 1, J = j + y - 1;
                        if (prf[I][J] + prf[i - 1][j - 1] - prf[I][j - 1] - prf[i - 1][J] == x * y) {
                            dmg[i][j] += 1;
                            dmg[I + 1][j] -= 1;
                            dmg[i][J + 1] -= 1;
                            dmg[I + 1][J + 1] += 1;
                        }
                    }
                }

                // if (x == 3 && y == 1) {
                //     cout << "\n";
                //     for (int i = 1; i <= n; ++i) 
                //         for (int j = 1; j <= m; ++j)
                //             cout << dmg[i][j] << " \n"[j == m]; 
                // }   

                for (int i = 1; i <= n; ++i)
                    for (int j = 1; j <= m; ++j)
                        dmg[i][j] += dmg[i - 1][j] + dmg[i][j - 1] - dmg[i - 1][j - 1];

                // if (x == 3 && y == 1) {
                //     cout << "\n";
                //     for (int i = 1; i <= n; ++i) 
                //         for (int j = 1; j <= m; ++j)
                //             cout << dmg[i][j] << " \n"[j == m]; 
                // }
                bool valid = 1;
                for (int i = 1; i <= n; ++i) {
                    for (int j = 1; j <= m; ++j) {
                        if (a[i][j] && !dmg[i][j])
                            valid = 0;
                    }
                }
                if (valid) ans = max(ans, x * y);
            }
        }

        cout << ans << "\n";
    }

}

• Subtask 1: 30 / 100