Submission #433531


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) 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 4024 Byte
Status WA
Exec Time 53 ms
Memory 928 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 17
WA × 5
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 50 ms 800 KB
sample-02.txt AC 53 ms 736 KB
test-01.txt AC 49 ms 800 KB
test-02.txt AC 48 ms 804 KB
test-03.txt AC 48 ms 804 KB
test-04.txt WA 52 ms 920 KB
test-05.txt AC 50 ms 928 KB
test-06.txt WA 51 ms 796 KB
test-07.txt AC 48 ms 812 KB
test-08.txt AC 49 ms 808 KB
test-09.txt AC 49 ms 800 KB
test-10.txt AC 50 ms 808 KB
test-11.txt AC 46 ms 924 KB
test-12.txt AC 48 ms 800 KB
test-13.txt WA 50 ms 812 KB
test-14.txt AC 50 ms 928 KB
test-15.txt WA 51 ms 728 KB
test-16.txt AC 50 ms 800 KB
test-17.txt WA 50 ms 800 KB
test-18.txt AC 48 ms 808 KB
test-19.txt AC 50 ms 796 KB
test-20.txt AC 48 ms 808 KB