結果
問題 | No.2456 Stamp Art |
ユーザー | Aeren |
提出日時 | 2023-09-01 23:22:12 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 256 ms / 5,000 ms |
コード長 | 1,923 bytes |
コンパイル時間 | 6,232 ms |
コンパイル使用メモリ | 379,760 KB |
実行使用メモリ | 38,616 KB |
最終ジャッジ日時 | 2023-09-02 11:20:35 |
合計ジャッジ時間 | 9,376 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 156 ms
38,432 KB |
testcase_04 | AC | 2 ms
4,384 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 200 ms
38,428 KB |
testcase_07 | AC | 199 ms
38,432 KB |
testcase_08 | AC | 193 ms
38,420 KB |
testcase_09 | AC | 208 ms
38,444 KB |
testcase_10 | AC | 244 ms
38,444 KB |
testcase_11 | AC | 183 ms
38,616 KB |
testcase_12 | AC | 221 ms
38,384 KB |
testcase_13 | AC | 256 ms
38,384 KB |
testcase_14 | AC | 246 ms
38,444 KB |
testcase_15 | AC | 159 ms
38,416 KB |
testcase_16 | AC | 88 ms
21,192 KB |
testcase_17 | AC | 2 ms
4,384 KB |
testcase_18 | AC | 1 ms
4,380 KB |
testcase_19 | AC | 98 ms
26,540 KB |
testcase_20 | AC | 245 ms
38,456 KB |
testcase_21 | AC | 206 ms
35,248 KB |
testcase_22 | AC | 219 ms
38,452 KB |
testcase_23 | AC | 8 ms
5,128 KB |
testcase_24 | AC | 16 ms
6,236 KB |
testcase_25 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> #include <x86intrin.h> using namespace std; using namespace numbers; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int nr, nc; cin >> nr >> nc; vector<string> a(nr); copy_n(istream_iterator<string>(cin), nr, a.begin()); vector<vector<int>> cnt(nr + 1, vector<int>(nc + 1)); for(auto x = 0; x < nr; ++ x){ for(auto y = 0; y < nc; ++ y){ cnt[x + 1][y + 1] = (a[x][y] == '#') + cnt[x][y + 1] + cnt[x + 1][y] - cnt[x][y]; } } auto count = [&](int xl, int xr, int yl, int yr)->int{ return cnt[xl][yl] - cnt[xl][yr] - cnt[xr][yl] + cnt[xr][yr]; }; vector<vector<int>> push(nr + 1, vector<int>(nc + 1)); cout << *ranges::partition_point(ranges::iota_view(1, min(nr, nc) + 1), [&](int k){ ranges::fill(push | ranges::views::join, 0); for(auto x = 0; x + k <= nr; ++ x){ for(auto y = 0; y + k <= nc; ++ y){ if(k * k == count(x, x + k, y, y + k)){ push[x][y] += 1; push[x][y + k] += -1; push[x + k][y] += -1; push[x + k][y + k] += 1; } } } for(auto x = 0; x < nr; ++ x){ for(auto y = 0; y < nc; ++ y){ push[x][y + 1] += push[x][y]; } } for(auto x = 0; x < nr; ++ x){ for(auto y = 0; y < nc; ++ y){ push[x + 1][y] += push[x][y]; } } for(auto x = 0; x < nr; ++ x){ for(auto y = 0; y < nc; ++ y){ if(!!push[x][y] != (a[x][y] == '#')){ return false; } } } return true; }) - 1 << "\n"; return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////