結果

問題 No.2456 Stamp Art
コンテスト
ユーザー 👑 binap
提出日時 2023-09-02 00:10:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 983 ms / 5,000 ms
コード長 1,904 bytes
コンパイル時間 4,269 ms
コンパイル使用メモリ 238,680 KB
実行使用メモリ 91,396 KB
最終ジャッジ日時 2024-06-11 18:10:48
合計ジャッジ時間 12,732 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:53:34: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   53 |                         for(auto [x, c] : event[y]){
      |                                  ^

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef pair<int,int> P;
typedef long double ld;

int main(){
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	rep(y, h) cin >> a[y];
	bool simple = true;
	rep(y, h) rep(x, w) if(a[y][x] == '.') simple = false;
	int m = min(h, w);
	if(simple){
		cout << m;
		return 0;
	}
	vector<vector<int>> imos(h + 1, vector<int>(w + 1));
	rep(y, h) rep(x, w){
		if(a[y][x] == '#') imos[y + 1][x + 1]++;
	}
	rep(y, h + 1) rep(x, w){
		imos[y][x + 1] += imos[y][x];
	}
	rep(y, h) rep(x, w + 1){
		imos[y + 1][x] += imos[y][x];
	}
	/*
	rep(y, h + 1){
		rep(x, w + 1) cout << imos[y][x]<< ' ';
		cout << "\n";
	}
	*/
	int left = 1, right = m;
	while(right - left > 1){
		int mid = (right + left) / 2;
		int mid2 = mid * mid;
		vector<vector<pair<int, int>>> event(h + 1);
		rep(y, h - mid + 1) rep(x, w - mid + 1){
			if(imos[y + mid][x + mid] - imos[y + mid][x] - imos[y][x + mid] + imos[y][x] == mid2) event[y].emplace_back(x, 1), event[y + mid].emplace_back(x, -1);
		}
		vector<int> base(w + 1);
		vector<vector<bool>> b(h, vector<bool>(w));
		rep(y, h){
			for(auto [x, c] : event[y]){
				base[x] += c;
				base[x + mid] -= c;
			}
			vector<int> res(w + 1);
			res[0] = base[0];
			rep(x, w) res[x + 1] = res[x] + base[x + 1];
			rep(x, w) if(res[x] > 0) b[y][x] = true;
		}
		/*
		cout << mid << "\n";
		rep(y, h){
			rep(x, w) cout << (b[y][x] ? 1 : 0 )<< ' ';
			cout << "\n";
		}
		*/
		bool success = true;
		rep(y, h) rep(x, w){
			if(a[y][x] == '#' and b[y][x] == false) success = false;
			if(a[y][x] == '.' and b[y][x] == true) success = false;
		}
		if(success) left = mid;
		else right = mid;
	}
	cout << left;
	return 0;
}
0