Submission #3016980


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)

typedef pair<int, int> pint;

#define L int(1e5)
#define INF 1e9;
vector<int> dp = vector<int>(1e5, - 1);
vector<int> tbl = vector<int>(9, 0);
int bs[2][3];
int cs[3][2];

int score(){
    int ret = 0;
    rep(i, 2){
        rep(j, 3){
           ret += tbl[i * 3 + j] == tbl[i * 3 + 3 + j] ? bs[i][j] : 0;
        }
    }

    rep(i, 3){
        rep(j, 2){
            ret += tbl[i * 3 + j] == tbl[i * 3 + 1 + j] ? cs[i][j] : 0;
        }
    }
    return ret;
}

int get_a(){
    int ret = 0;
    int f = 1;
    rep(i, 9){
        ret += tbl[i] * f;
        f *= 3;
    }
    return ret;
}

int rec(int t){
    int a = get_a();
    if(dp[a] !=  - 1){
        return dp[a];
    }
    if(t == 9){
        return dp[a] = score();
    }

    int ret =  -1;

    if(t % 2 == 0){
        rep(i, 9){
            if(! tbl[i]) {
                tbl[i] = 1;
                ret = max(ret, rec(t + 1));
                tbl[i] = 0;
            }
        }
        return dp[a] = ret;
    }

    ret = INF;
    if(t % 2){
        rep(i, 9){
            if(! tbl[i]){
                tbl[i] = 2;
                ret = min(ret, rec(t + 1));
                tbl[i] = 0;
            }
        }
        return dp[a] = ret;
    }
}


int main() {
    int sum = 0;
    rep(i, 2){
        rep(j, 3){
            cin >> bs[i][j];
            sum += bs[i][j];
        }
    }

    rep(i, 3){
        rep(j, 2){
            cin >> cs[i][j];
            sum += cs[i][j];
        }
    }

    int ans = rec(0);

    cout << ans << endl;
    cout << sum - ans << endl;

    return 0;

}

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User zakou
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1815 Byte
Status AC
Exec Time 2 ms
Memory 640 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 2 ms 640 KB
sample-02.txt AC 2 ms 640 KB
test-01.txt AC 2 ms 640 KB
test-02.txt AC 2 ms 640 KB
test-03.txt AC 2 ms 640 KB
test-04.txt AC 2 ms 640 KB
test-05.txt AC 2 ms 640 KB
test-06.txt AC 2 ms 640 KB
test-07.txt AC 2 ms 640 KB
test-08.txt AC 2 ms 640 KB
test-09.txt AC 2 ms 640 KB
test-10.txt AC 2 ms 640 KB
test-11.txt AC 2 ms 640 KB
test-12.txt AC 2 ms 640 KB
test-13.txt AC 2 ms 640 KB
test-14.txt AC 2 ms 640 KB
test-15.txt AC 2 ms 640 KB
test-16.txt AC 2 ms 640 KB
test-17.txt AC 2 ms 640 KB
test-18.txt AC 2 ms 640 KB
test-19.txt AC 2 ms 640 KB
test-20.txt AC 2 ms 640 KB