Submission #434043
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
#define FOREQ(i,a,b) for(int i = a; i <= (int)b; i++)
#define FOREACH(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define ALL(c) (c).begin(), (c).end()
#define SZ(c) (c).size()
template <class T> void pp(T v) { FOREACH(it, v) cout << *it << ' '; cout << endl ; }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef complex<double> P;
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef unsigned uint;
const int INF = 1<<28;
const double EPS = 1.0e-9;
static const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
#undef MOD_CALC
#ifdef MOD_CALC
const ll MOD = 1000 * 1000 * 1000 + 7 ; // 1000000007
inline void chadd(ll &a, const ll b) { a = (a + b) % MOD;}
inline ll add(const ll a, const ll b){ return (a + b) % MOD;}
inline void chsub(ll &a, const ll b) { a = (a - b + MOD) % MOD;}
inline ll sub(const ll a, const ll b){ return (a - b + MOD) % MOD; }
inline void chmul(ll &a, const ll b) { a = (a * b) % MOD;}
inline ll mul(const ll a, const ll b){ return (a * b) % MOD;}
#endif
int brd[3][3];
int naohiro_score[1<<9];
int naoko_score[1<<9];
pint dfs(const int depth) {
int naohiro = 0, naoko = 0, x, y;
if(depth >= 8) {
REP(i, 3) REP(j, 3) if(brd[i][j] == -1) {
y = i; x = j;
}
brd[y][x] = 1;
int pat = 0;
REP(i, 3) REP(j, 3) {
if(brd[i][j] == 1)
pat |= (brd[i][j] << (i * 3 + j));
}
naohiro = naohiro_score[pat];
naoko = naoko_score[pat];
brd[y][x] = -1;
}
else if(depth % 2 == 0) { // naohiro
REP(i, 3) REP(j, 3) {
if(brd[i][j] == -1) {
brd[i][j] = 1;
pint tmp = dfs(depth+1);
if(tmp.first > naohiro) {
naohiro = tmp.first;
naoko = tmp.second;
}
brd[i][j] = -1;
}
}
} else { // naoko
REP(i, 3) REP(j, 3) {
if(brd[i][j] == -1) {
brd[i][j] = 0;
pint tmp = dfs(depth+1);
if(tmp.second > naoko) {
naohiro = tmp.first;
naoko = tmp.second;
}
brd[i][j] = -1;
}
}
}
return make_pair(naohiro, naoko);
}
int main(void)
{
int b[2][3], c[3][2], game[3][3];
REP(i,2) REP(j,3) cin>>b[i][j];
REP(i,3) REP(j,2) cin>>c[i][j];
REP(pat, 1<<9) {
if(__builtin_popcount (pat) == 5) {
REP(i,3) REP(j,3) game[i][j] = ((pat >> (i*3 + j)) & 1);
int naohiro = 0, naoko = 0;
REP(i, 2) REP(j, 3) {
if(game[i][j] == game[i+1][j]) naohiro += b[i][j];
else naoko += b[i][j];
}
REP(i, 3) REP(j, 2) {
if(game[i][j] == game[i][j+1]) naohiro += c[i][j];
else naoko += c[i][j];
}
naohiro_score[pat] = naohiro;
naoko_score[pat] = naoko;
//printf("%x %d %d", pat, naohiro_score[pat], naoko_score[pat]);
//puts("");
}
}
REP(i,3) REP(j,3) brd[i][j] = -1;
pair<int, int> ans = dfs(0);
cout << ans.first << endl;
cout << ans.second << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 双子と○×ゲーム |
User |
kmatsunaga |
Language |
C++ (GCC 4.9.2) |
Score |
0 |
Code Size |
4086 Byte |
Status |
WA |
Exec Time |
68 ms |
Memory |
924 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
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 |
66 ms |
800 KB |
sample-02.txt |
AC |
68 ms |
768 KB |
test-01.txt |
AC |
66 ms |
804 KB |
test-02.txt |
AC |
66 ms |
804 KB |
test-03.txt |
AC |
64 ms |
920 KB |
test-04.txt |
WA |
66 ms |
800 KB |
test-05.txt |
AC |
64 ms |
800 KB |
test-06.txt |
WA |
64 ms |
924 KB |
test-07.txt |
AC |
65 ms |
748 KB |
test-08.txt |
AC |
66 ms |
808 KB |
test-09.txt |
AC |
65 ms |
804 KB |
test-10.txt |
AC |
68 ms |
808 KB |
test-11.txt |
AC |
63 ms |
924 KB |
test-12.txt |
AC |
66 ms |
924 KB |
test-13.txt |
WA |
68 ms |
924 KB |
test-14.txt |
AC |
67 ms |
728 KB |
test-15.txt |
WA |
66 ms |
800 KB |
test-16.txt |
AC |
64 ms |
800 KB |
test-17.txt |
WA |
67 ms |
804 KB |
test-18.txt |
AC |
66 ms |
920 KB |
test-19.txt |
AC |
67 ms |
800 KB |
test-20.txt |
AC |
67 ms |
800 KB |