Submission #2142236


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
#define NOTUSED 0
#define CHOKUDAI 1
#define NAOKO -1

using namespace std;

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

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

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

	int maxScore = -1, minScore = INF;
	rep (i, 9){
		if (hand[i] == CHOKUDAI || hand[i] == NAOKO) continue;
		if (handNum % 2 == 0){	// chokudai's hand
			hand[i] = CHOKUDAI;
			maxScore = max(maxScore, dfs(hand, handNum + 1));
			hand[i] = NOTUSED;
		}else{				// naoko's hand
			hand[i] = NAOKO;
			minScore = min(minScore, dfs(hand, handNum + 1));
			hand[i] = NOTUSED;
		} // end if
	} // end rep
	return (handNum % 2 == 0 ? maxScore : minScore);
}

int main()
{
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	rep (i, 2) rep (j, 3) cin >> b[i][j];
	rep (i, 3) rep (j, 2) cin >> c[i][j];

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

	int hand[9] = {NOTUSED};
	int chokudaiScore = dfs(hand, 0);
	
	cout << chokudaiScore << endl;
	cout << sum - chokudaiScore << endl;

	return 0;
}

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User ty70
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1616 Byte
Status AC
Exec Time 29 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 24
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
sample-01.txt AC 29 ms 256 KB
sample-02.txt AC 29 ms 256 KB
test-01.txt AC 29 ms 256 KB
test-02.txt AC 29 ms 256 KB
test-03.txt AC 29 ms 256 KB
test-04.txt AC 29 ms 256 KB
test-05.txt AC 29 ms 256 KB
test-06.txt AC 29 ms 256 KB
test-07.txt AC 29 ms 256 KB
test-08.txt AC 29 ms 256 KB
test-09.txt AC 29 ms 256 KB
test-10.txt AC 29 ms 256 KB
test-11.txt AC 29 ms 256 KB
test-12.txt AC 29 ms 256 KB
test-13.txt AC 29 ms 256 KB
test-14.txt AC 29 ms 256 KB
test-15.txt AC 29 ms 256 KB
test-16.txt AC 29 ms 256 KB
test-17.txt AC 29 ms 256 KB
test-18.txt AC 29 ms 256 KB
test-19.txt AC 29 ms 256 KB
test-20.txt AC 29 ms 256 KB