Submission #3859510

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

typedef long long ll;
typedef pair<int, int> P;


int b[2][3];
int c[3][2];

map<string,int> memo;

int dfs(string curr, int depth){

	if (memo.count(curr)){
		return memo[curr];
	} // end if

	if (depth == 9){
		int sum = 0;
		rep (i, 2){
			rep (j, 3){
				if (curr[i * 3 + j] == curr[(i + 1) * 3 + j]){
					sum += b[i][j];
				} // end if
			} // end rep
		} // end rep
		rep (i, 3){
			rep (j, 2){
				if (curr[i * 3 + j] == curr[i * 3 + (j + 1)]){
					sum += c[i][j];
				} // end if
			} // end rep
		} // end rep
		return sum;
	} // end if

	int maxScore = -1, minScore = INF;
	rep (i, 9){
		if (curr[i] == '.'){
			if (depth % 2 == 0){
				curr[i] = 'o';
				maxScore = max(maxScore, dfs(curr, depth + 1));
			}else{
				curr[i] = 'x';
				minScore = min(minScore, dfs(curr, depth + 1));
			} // end if
			curr[i] = '.';
		} // end if
	} // end rep

	return memo[curr] = (depth % 2 == 0 ? maxScore : minScore);
}

int main()
{
	rep (i, 2) rep (j, 3) b[i][j] = 0, c[j][i] = 0;

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int sum = 0;
	rep (i, 2) rep (j, 3) cin >> b[i][j], sum += b[i][j];
	rep (i, 3) rep (j, 2) cin >> c[i][j], sum += c[i][j];

	string board = ".........";
	int res = dfs(board, 0);

	cout << res << endl;
	cout << sum - res << endl;

	return 0;
}

Submission Info

Judge Result