結果

問題 No.861 ケーキカット
コンテスト
ユーザー QCFium
提出日時 2019-08-09 22:18:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,099 bytes
コンパイル時間 1,594 ms
コンパイル使用メモリ 175,016 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-19 12:17:00
合計ジャッジ時間 3,069 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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;
			}
		}
	}
}

int a[5][5];

int64_t dfs(int i, int prev, int64_t sub) {
	if (i == 5) return sub;
	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];
		res = std::min(res, std::abs(dfs(i + 1, j, sub_cur)));
	}
	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