結果
問題 | No.2456 Stamp Art |
ユーザー |
![]() |
提出日時 | 2023-08-03 00:10:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 359 ms / 5,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 2,103 ms |
コンパイル使用メモリ | 206,240 KB |
最終ジャッジ日時 | 2025-02-15 21:31:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int H, W; vector<vector<int>> v; vector<string> S; bool solve(int X){ vector<vector<int>> w(H+2, vector<int>(W+2)); for (int i=1; i<=H-X+1; i++){ for (int j=1; j<=W-X+1; j++){ if (v[i+X-1][j+X-1]-v[i+X-1][j-1]-v[i-1][j+X-1]+v[i-1][j-1] == X*X){ w[i][j]++; w[i+X][j]--; w[i][j+X]--; w[i+X][j+X]++; } } } for (int i=0; i<=H; i++){ for (int j=1; j<=W; j++){ w[i][j] += w[i][j-1]; } } for (int i=1; i<=H; i++){ for (int j=0; j<=W; j++){ w[i][j] += w[i-1][j]; } } for (int i=1; i<=H; i++){ for (int j=1; j<=W; j++){ if (S[i-1][j-1] == '#' && w[i][j] == 0) return 0; } } return 1; } int main(){ cin >> H >> W; S.resize(H); for (int i=0; i<H; i++) cin >> S[i]; v.resize(H+1, vector<int>(W+1)); for (int i=1; i<=H; i++){ for (int j=1; j<=W; j++){ if (S[i-1][j-1] == '#') v[i][j]++; v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1]; } } int l=1, r=min(H, W)+1, c; while(r-l>1){ c = (r+l)/2; if (solve(c)) l=c; else r=c; } cout << l << endl; return 0; }