Submission #1128285
Source Code Expand
#include "bits/stdc++.h"
#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v),v.end()));
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9
const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
/*
pair<int, int> dfs(vvi &b, vvi&c, vvi state, int turn) {
if (turn == 9) {
int A = 0, B = 0;
REP(i, 2) {
REP(j, 3) {
if (state[i][j] == state[i + 1][j])A += b[i][j];
else B += b[i][j];
}
}
REP(i, 3) {
REP(j, 2) {
if (state[i][j] == state[i][j + 1])A += c[i][j];
else B += c[i][j];
}
}
return{ A,B };
}
if (turn % 2 == 1) {
vi x, y;
int cmax = -1;
vector<pair<int, int>> v;
REP(i, 3) {
REP(j, 3) {
if (state[i][j] == 0) {
if (i != 2 && state[i + 1][j] == -1 && b[i][j] >= cmax) {
x.push_back(j);
y.push_back(i + 1);
cmax = b[i][j];
}
if (i != 0 && state[i - 1][j] == -1 && b[i - 1][j] >= cmax) {
x.push_back(j);
y.push_back(i - 1);
cmax = b[i - 1][j];
}
if (j != 2 && state[i][j + 1] == -1 && c[i][j] >= cmax) {
x.push_back(j + 1);
y.push_back(i);
cmax = c[i][j];
}
if (j != 0 && state[i][j - 1] == -1 && c[i][j - 1] >= cmax) {
x.push_back(j - 1);
y.push_back(i);
cmax = c[i][j - 1];
}
}
}
}
REP(i, x.size()) {
auto tmp = state;
tmp[y[i]][x[i]] = 1;
v.push_back(dfs(b, c, tmp, turn + 1));
}
int A = -INF, B = -INF;
REP(i, v.size()) {
if (B < v[i].second) {
B = v[i].second;
A = v[i].first;
}
}
return{ A,B };
}
else {
vi x, y;
int cmax = -1;
vector<pair<int, int>> v;
REP(i, 3) {
REP(j, 3) {
if (state[i][j] == 0) {
if (i != 2 && state[i + 1][j] == -1 && b[i][j] >= cmax) {
x.push_back(j);
y.push_back(i + 1);
cmax = b[i][j];
}
if (i != 0 && state[i - 1][j] == -1 && b[i - 1][j] >= cmax) {
x.push_back(j);
y.push_back(i - 1);
cmax = b[i - 1][j];
}
if (j != 2 && state[i][j + 1] == -1 && c[i][j] >= cmax) {
x.push_back(j + 1);
y.push_back(i);
cmax = c[i][j];
}
if (j != 0 && state[i][j - 1] == -1 && c[i][j - 1] >= cmax) {
x.push_back(j - 1);
y.push_back(i);
cmax = c[i][j - 1];
}
}
}
}
REP(i, x.size()) {
auto tmp = state;
tmp[y[i]][x[i]] = 0;
v.push_back(dfs(b, c, tmp, turn + 1));
}
int A = -INF, B = -INF;
REP(i, v.size()) {
if (A < v[i].first) {
B = v[i].second;
A = v[i].first;
}
}
return{ A,B };
}
}
*/
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
vvi b(2, vi(3)), c(3, vi(2));
const int n = 59049;
pair<int, int> dp[n + 1];
pair<int, int> dfs(vvi state, int turn) {
int p = 0;
REP(i, 3) {
REP(j, 3) {
p += state[i][j] + 1;
p *= 3;
}
}
if (dp[p].first != -1)return dp[p];
if (turn == 9) {
int A = 0, B = 0;
REP(i, 2) {
REP(j, 3) {
if (state[i][j] == state[i + 1][j])A += b[i][j];
else B += b[i][j];
}
}
REP(i, 3) {
REP(j, 2) {
if (state[i][j] == state[i][j + 1])A += c[i][j];
else B += c[i][j];
}
}
return dp[p] = { A,B };
}
if (turn % 2 == 1) {
vector<pair<int, int>> v;
REP(i, 3) {
REP(j, 3) {
if (state[i][j] == -1) {
auto tmp = state;
tmp[i][j] = 1;
v.push_back(dfs(tmp, turn + 1));
}
}
}
int A = -INF, B = -INF;
REP(i, v.size()) {
if (B < v[i].second) {
A = v[i].first;
B = v[i].second;
}
}
return dp[p] = { A,B };
}
else {
vector<pair<int, int>> v;
REP(i, 3) {
REP(j, 3) {
if (state[i][j] == -1) {
auto tmp = state;
tmp[i][j] = 0;
v.push_back(dfs(tmp, turn + 1));
}
}
}
int A = -INF, B = -INF;
REP(i, v.size()) {
if (A < v[i].first) {
A = v[i].first;
B = v[i].second;
}
}
return dp[p] = { A,B };
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
REP(i, 2)REP(j, 3)cin >> b[i][j];
REP(i, 3)REP(j, 2)cin >> c[i][j];
REP(i, n+1)dp[i] = { -1,-1 };
int cmax = -1;
pair<int, int> ans;
REP(i, 3) {
REP(j, 3) {
vvi tmp(3, vi(3, -1));
tmp[i][j] = 0;
auto p = dfs(tmp, 1);
if (p.first > cmax) {
ans = p;
cmax = p.first;
}
}
}
cout << ans.first << endl << ans.second << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 双子と○×ゲーム |
User |
etonagisa |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4974 Byte |
Status |
AC |
Exec Time |
10 ms |
Memory |
768 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
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 |
10 ms |
768 KB |
sample-02.txt |
AC |
10 ms |
768 KB |
test-01.txt |
AC |
10 ms |
768 KB |
test-02.txt |
AC |
10 ms |
768 KB |
test-03.txt |
AC |
10 ms |
768 KB |
test-04.txt |
AC |
10 ms |
768 KB |
test-05.txt |
AC |
10 ms |
768 KB |
test-06.txt |
AC |
10 ms |
768 KB |
test-07.txt |
AC |
10 ms |
768 KB |
test-08.txt |
AC |
10 ms |
768 KB |
test-09.txt |
AC |
10 ms |
768 KB |
test-10.txt |
AC |
10 ms |
768 KB |
test-11.txt |
AC |
10 ms |
768 KB |
test-12.txt |
AC |
10 ms |
768 KB |
test-13.txt |
AC |
10 ms |
768 KB |
test-14.txt |
AC |
10 ms |
768 KB |
test-15.txt |
AC |
10 ms |
768 KB |
test-16.txt |
AC |
10 ms |
768 KB |
test-17.txt |
AC |
9 ms |
768 KB |
test-18.txt |
AC |
10 ms |
768 KB |
test-19.txt |
AC |
10 ms |
768 KB |
test-20.txt |
AC |
10 ms |
768 KB |