結果

問題 No.2456 Stamp Art
ユーザー 👑 hos.lyrichos.lyric
提出日時 2023-09-01 22:10:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 148 ms / 5,000 ms
コード長 2,344 bytes
コンパイル時間 947 ms
コンパイル使用メモリ 98,992 KB
実行使用メモリ 38,920 KB
最終ジャッジ日時 2023-09-02 11:17:56
合計ジャッジ時間 4,626 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,620 KB
testcase_01 AC 2 ms
5,724 KB
testcase_02 AC 2 ms
5,628 KB
testcase_03 AC 130 ms
31,072 KB
testcase_04 AC 2 ms
5,504 KB
testcase_05 AC 3 ms
5,564 KB
testcase_06 AC 148 ms
35,512 KB
testcase_07 AC 108 ms
38,704 KB
testcase_08 AC 102 ms
38,908 KB
testcase_09 AC 131 ms
38,324 KB
testcase_10 AC 123 ms
37,856 KB
testcase_11 AC 121 ms
35,536 KB
testcase_12 AC 106 ms
38,900 KB
testcase_13 AC 140 ms
38,808 KB
testcase_14 AC 122 ms
38,920 KB
testcase_15 AC 113 ms
31,012 KB
testcase_16 AC 86 ms
32,728 KB
testcase_17 AC 2 ms
5,548 KB
testcase_18 AC 2 ms
5,460 KB
testcase_19 AC 71 ms
26,748 KB
testcase_20 AC 129 ms
38,888 KB
testcase_21 AC 119 ms
38,792 KB
testcase_22 AC 132 ms
38,036 KB
testcase_23 AC 24 ms
25,696 KB
testcase_24 AC 18 ms
17,440 KB
testcase_25 AC 2 ms
5,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int M, N;
char A[2010][2010];

int S[2010][2010];
int get(int x0, int x1, int y0, int y1) {
  return S[x0][y0] - S[x0][y1] - S[x1][y0] + S[x1][y1];
}

int f[2010][2010];
bool check(int k) {
  for (int x = 0; x <= M - k; ++x) for (int y = 0; y <= N - k; ++y) {
    f[x + 1][y + 1] = f[x + 1][y] + f[x][y + 1] - f[x][y] + (get(x, x + k, y, y + k) ? 0 : 1);
  }
  for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) if (A[x][y] == '#') {
    int x0 = x - k + 1, x1 = x + 1;
    int y0 = y - k + 1, y1 = y + 1;
    chmax(x0, 0); chmin(x1, M - k + 1);
    chmax(y0, 0); chmin(y1, N - k + 1);
    if (f[x0][y0] - f[x0][y1] - f[x1][y0] + f[x1][y1] == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  for (; ~scanf("%d%d", &M, &N); ) {
    for (int x = 0; x < M; ++x) {
      scanf("%s", A[x]);
    }
    
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
      S[x + 1][y + 1] = S[x + 1][y] + S[x][y + 1] - S[x][y] + ((A[x][y] == '.') ? 1 : 0);
    }
    int lo = 0, hi = min(M, N) + 1;
    for (; lo + 1 < hi; ) {
      const int mid = (lo + hi) / 2;
      (check(mid) ? lo : hi) = mid;
    }
    printf("%d\n", lo);
  }
  return 0;
}
0