結果

問題 No.2456 Stamp Art
ユーザー rniyarniya
提出日時 2023-09-01 22:35:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 881 ms / 5,000 ms
コード長 3,286 bytes
コンパイル時間 2,202 ms
コンパイル使用メモリ 208,880 KB
実行使用メモリ 54,796 KB
最終ジャッジ日時 2023-09-02 11:18:47
合計ジャッジ時間 15,843 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 736 ms
54,624 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 780 ms
54,624 KB
testcase_07 AC 785 ms
54,624 KB
testcase_08 AC 804 ms
54,796 KB
testcase_09 AC 826 ms
54,604 KB
testcase_10 AC 862 ms
54,604 KB
testcase_11 AC 787 ms
54,592 KB
testcase_12 AC 855 ms
54,604 KB
testcase_13 AC 881 ms
54,620 KB
testcase_14 AC 866 ms
54,652 KB
testcase_15 AC 744 ms
54,608 KB
testcase_16 AC 383 ms
28,928 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 232 ms
37,364 KB
testcase_20 AC 874 ms
54,608 KB
testcase_21 AC 761 ms
49,644 KB
testcase_22 AC 857 ms
54,560 KB
testcase_23 AC 12 ms
5,956 KB
testcase_24 AC 27 ms
7,552 KB
testcase_25 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <typename T> struct CumulativeSum2D {
    CumulativeSum2D(const std::vector<std::vector<T>>& v) {
        n = v.size(), m = v[0].size();
        dat.assign(n + 1, std::vector<T>(m + 1, T(0)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dat[i + 1][j + 1] = v[i][j];
                dat[i + 1][j + 1] += dat[i + 1][j] + dat[i][j + 1] - dat[i][j];
            }
        }
    }

    T query(int xl, int xr, int yl, int yr) const {  // [xl, xr) * [yl, yr)
        assert(0 <= xl && xl <= xr && xr <= n);
        assert(0 <= yl && yl <= yr && yr <= m);
        return dat[xr][yr] - dat[xl][yr] - dat[xr][yl] + dat[xl][yl];
    }

private:
    int n, m;
    std::vector<std::vector<T>> dat;
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    cin >> S;

    vector v(H, vector<int>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            v[i][j] = (S[i][j] == '#');
        }
    }
    CumulativeSum2D CS(v);
    auto check = [&](int x) -> bool {
        vector imos(H + 1, vector<int>(W + 1, 0));
        for (int i = 0; i + x <= H; i++) {
            for (int j = 0; j + x <= W; j++) {
                if (CS.query(i, i + x, j, j + x) == x * x) {
                    imos[i][j]++;
                    imos[i + x][j]--;
                    imos[i][j + x]--;
                    imos[i + x][j + x]++;
                }
            }
        }
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                imos[i][j + 1] += imos[i][j];
            }
        }
        for (int j = 0; j < W; j++) {
            for (int i = 0; i < H; i++) {
                imos[i + 1][j] += imos[i][j];
            }
        }
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                int x = (S[i][j] == '#'), y = (imos[i][j] > 0);
                if (x != y) return false;
            }
        }
        return true;
    };
    int lb = 0, ub = min(H, W) + 1;
    while (ub - lb > 1) {
        int mid = (ub + lb) >> 1;
        (check(mid) ? lb : ub) = mid;
    }

    cout << lb << '\n';
    return 0;
}
0