結果

問題 No.3410 Happiest Art
コンテスト
ユーザー Unbakedbread
提出日時 2025-11-25 22:00:34
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,617 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,337 ms
コンパイル使用メモリ 291,596 KB
実行使用メモリ 563,712 KB
最終ジャッジ日時 2025-12-16 23:30:43
合計ジャッジ時間 15,060 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 12 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int N, U;
	cin >> N >> U;
	int H, W;
	cin >> H >> W;
	
	//「m[絵]=kazuppaの幸福度」のmapを作る
	map<vector<ll>, int> m;
	for(int p = 0; p < N; ++p) {
		int F;
		cin >> F;
		vector<ll> A(H);
		for(int i = 0; i < H; ++i) {
			string S;
			cin >> S;
			for(int j = 0; j < W; ++j) if(S[j] == '#') A[i] ^= (1LL << j);
		}
		
		int kiyo = (p < U ? 1 : -1);
		m[A] += kiyo;
		if(F == 1) {
			for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) {
				A[i] ^= (1LL << j);
				m[A] += kiyo;
				A[i] ^= (1LL << j);
			}
		}
	}
	
	int ans = -1e9, last = H * W * N + 1;
	vector<ll> v;
	
	//mapにない絵を構築してもらう
	//mapにない絵があるならansは0になりvはその絵、そうでなかったらansは-1e9のまま
	auto koutiku = [&](auto &&koutiku, int t, int &l) ->void {
		if(t == H) {
			if(m.find(v) == m.end()) ans = 0, l = -1; //みつかった
			else --l;
			return;
		}
		
		for(ll bit = 0; bit < (1LL << W); ++bit) {
			v.push_back(bit);
			koutiku(koutiku, t + 1, l);
			if(l < 0) return; //みつかってたらすぐ終わらせる
			v.pop_back();
			if(l == 0) return; //個数がなくなったら終わり
		}
	};
	
	koutiku(koutiku, 0, last);
	
	//mapの中を見ていく
	for(auto [vec, val] : m) {
		if(ans <= val) {
			ans = val;
			v = vec;
		}
	}
	
	//出力
	cout << ans << "\n";
	for(int i = 0; i < H; ++i) {
		for(int j = 0; j < W; ++j) cout << (v[i] >> j & 1 ? '#': '.');
		cout << "\n";
	}
	return 0;
}
0