結果
問題 | No.2456 Stamp Art |
ユーザー |
|
提出日時 | 2023-09-01 23:01:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,501 bytes |
コンパイル時間 | 2,147 ms |
コンパイル使用メモリ | 194,780 KB |
最終ジャッジ日時 | 2025-02-16 17:12:46 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 7 WA * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main () {int H, W;cin >> H >> W;int A[4040][4040];char C[2020][2020];for (int i = 0; i < H; i ++) {for (int j = 0; j < W; j ++) {char c;cin >> c;A[i][j] = c == '#';C[i][j] = c;}}int ng = min(H, W) + 1, ok = 1;for (int i = 0; i < H + ng; i ++) {for (int j = 0; j < W + ng; j ++) {if (i < H && j < W) continue;A[i][j] = 0;}}for (int i = 0; i < H + ng; i ++) {for (int j = 1; j < W + ng; j ++) {A[i][j] += A[i][j - 1];}}for (int j = 0; j < W + ng; j ++) {for (int i = 1; i < H + ng; i ++) {A[i][j] += A[i - 1][j];}}int B[4040][4040];while (abs(ok - ng) > 1) {int mu = (ok + ng) / 2;for (int i = 0; i < H; i ++) {for (int j = 0; j < W; j ++) {B[i][j] = 0;}}for (int i = 0; i < H; i ++) {for (int j = 0; j < W; j ++) {if (A[i][j] + A[i + mu][j + mu] - A[i][j + mu] - A[i + mu][j] >= mu * mu) {B[i][j] ++;B[i + mu][j] --;B[i][j + mu] --;B[i + mu][j + mu] ++;}}}for (int i = 0; i < H; i ++) {for (int j = 1; j < W; j ++) {B[i][j] += B[i][j - 1];}}for (int j = 0; j < W; j ++) {for (int i = 1; i < H; i ++) {B[i][j] += B[i - 1][j];}}bool cn = true;for (int i = 0; i < H; i ++) {for (int j = 0; j < W; j ++) {if (C[i][j] == '#') {cn = cn && B[i][j] > 0;}}}if (cn) {ok = mu;} else {ng = mu;}}cout << ok << endl;}