Submission #1606901

---

Source Code Expand

#include <iostream>
using namespace std;

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

struct State{
    int a[3][3];
    int num;
};

int encode(int a[3][3]){
    int enc = 0;
    int fac = 1;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            enc += a[i][j] * fac;
            fac *= 3;
        }
    }
    return enc;
}

int calc(int a[3][3]){
    int ret = 0;
    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            if(a[i][j] == a[i+1][j])
                ret += b[i][j];
    for(int i=0; i<3; i++)
        for(int j=0; j<2; j++)
            if(a[i][j] == a[i][j+1])
                ret += c[i][j];
    return ret;
}

int dfs(State &state){
    int enc = encode(state.a);
    if(dp[enc] != -1) return dp[enc];
    if(state.num == 9){
        dp[enc] = calc(state.a);
        return dp[enc];
    }
    bool tak = !(state.num % 2);
    int optscore = tak ? -(1<<20) : 1<<20;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(state.a[i][j] == 0){
                state.a[i][j] = (state.num % 2) + 1;
                state.num++;
                int score = dfs(state);
                if(tak)
                    optscore = max(optscore, score);
                else
                    optscore = min(optscore, score);
                state.num--;
                state.a[i][j] = 0;
            }
        }
    }
    dp[enc] = optscore;
    return dp[enc];
}

int main(){
    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            cin >> b[i][j];
    for(int i=0; i<3; i++)
        for(int j=0; j<2; j++)
            cin >> c[i][j];

    fill_n(dp, 20000, -1);

    State state;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            state.a[i][j] = 0;
    state.num = 0;
    dfs(state);

    int sm = 0;
    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            sm += b[i][j] + c[j][i];
    cout << dp[0] << endl;
    cout << sm - dp[0] << endl;
    return 0;
}

Submission Info

Judge Result