結果

問題 No.861 ケーキカット
コンテスト
ユーザー QCFium
提出日時 2019-08-09 22:24:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,068 bytes
コンパイル時間 1,876 ms
コンパイル使用メモリ 176,776 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-19 12:27:29
合計ジャッジ時間 35,446 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 3
other TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int64_t rll() {
	long long n;
	scanf("%lld", &n);
	return n;
}

bool ok[32][32];
void init() {
	for (int i = 0; i < 1 << 5; i++) {
		for (int j = 0; j < 1 << 5; j++) {
			if (!i) ok[i][j] = true;
			else if (!j) ok[i][j] = false;
			else {
				bool a[2][5];
				for (int k = 0; k < 5; k++) a[0][k] = i >> k & 1;
				for (int k = 0; k < 5; k++) a[1][k] = j >> k & 1;
				std::queue<std::pair<int, int> > que;
				bool used[2][5] = {{ 0 }};
				for (int k = 0; k < 5; k++) {
					if (a[0][k]) {
						used[0][k] = true;
						que.push({0, k});
					}
				}
				assert(que.size());
				while (que.size()) {
					auto cur = que.front();
					que.pop();
					if (!cur.first) {
						if (a[1][cur.second] && !used[1][cur.second]) {
							used[1][cur.second] = true;
							que.push({1, cur.second});
						}
					} else {
						if (a[0][cur.second] && !used[0][cur.second]) {
							used[0][cur.second] = true;
							que.push({0, cur.second});
						}
					}
					if (cur.second && a[cur.first][cur.second - 1] && !used[cur.first][cur.second - 1]) {
						used[cur.first][cur.second - 1] = true;
						que.push({cur.first, cur.second - 1});
					}
					if (cur.second < 4 && a[cur.first][cur.second + 1] && !used[cur.first][cur.second + 1]) {
						used[cur.first][cur.second + 1] = true;
						que.push({cur.first, cur.second + 1});
					}
				}
				ok[i][j] = true;
				for (int k = 0; k < 2; k++) 
					for (int l = 0; l < 5; l++) if (a[k][l] && !used[k][l]) ok[i][j] = false;
			}
		}
	}
}

bool is_connected(const std::vector<int> &a) {
	assert(a.size() == 5);
	bool used[5][5] = { { 0 } };
	std::queue<std::pair<int, int> > que;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (a[i] >> j & 1) {
				used[i][j] = true;
				que.push({i, j});
			}
		}
	}
	while (que.size()) {
		auto cur = que.front();
		que.pop();
		static const std::pair<int, int> dirs[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		for (auto d : dirs) {
			int x = cur.first + d.first;
			int y = cur.second + d.second;
			if (x < 0 || x >= 5) continue;
			if (y < 0 || y >= 5) continue;
			if (!(a[x] >> y & 1)) continue;
			if (!used[x][y]) {
				used[x][y] = true;
				que.push({x, y});
			}
		}
	}
	for (int i = 0; i < 5; i++) 
		for (int j = 0; j < 5; j++) if ((a[i] >> j & 1) && !used[i][j]) return false;
	return true;
}

int a[5][5];

std::vector<int> stack;
int64_t dfs(int i, int prev, int64_t sub) {
	if (i == 5) {
		assert(stack.size() == 5);
		return is_connected(stack) ? sub : 100000000000000000;
	}
	int64_t res = 100000000000000000;
	for (int j = 0; j < 1 << 5; j++) {
		if (!ok[prev][j]) continue;
		int64_t sub_cur = sub;
		for (int k = 0; k < 5; k++) if (j >> k & 1) sub_cur += a[i][k]; else sub_cur -= a[i][k];
		stack.push_back(j);
		res = std::min(res, std::abs(dfs(i + 1, j, sub_cur)));
		stack.pop_back();
	}
	return res;
}

int main() {
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++) a[i][j] = ri();
	init();
	
	std::cout << dfs(0, 0, 0) << std::endl;
	
	return 0;
}
0