Submission #1026836


Source Code Expand


def calc():
    t = 0
    for y in range(2):
        for x in range(3):
            if field[y][x] == field[y + 1][x]:
                t += score_b[y][x]
            if field[x][y] == field[x][y + 1]:
                t += score_c[x][y]
    return t


memo = {}
def dfs(i):
    key = tuple([tuple(field[0]), tuple(field[1]), tuple(field[2])])
    if i == 9:
        return calc()

    if key in memo:
        return memo[key]

    p = i % 2
    best_score = -1 if p == 0 else 10 ** 10
    for y in range(3):
        for x in range(3):
            if field[y][x] is not None:
                continue

            field[y][x] = p
            tmp_score = dfs(i + 1)

            if p == 0:
                best_score = max(best_score, tmp_score)

            if p == 1:
                best_score = min(best_score, tmp_score)

            field[y][x] = None

    memo[key] = best_score
    return best_score

if __name__ == '__main__':
    score_b = [[int(s) for s in input().split()] for _ in range(2)]
    score_c = [[int(s) for s in input().split()] for _ in range(3)]
    total = sum([sum(l) for l in score_b]) + sum([sum(l) for l in score_c])

    field = [[None] * 3 for _ in range(3)]
    t = dfs(0)
    print(t)
    print(total - t)

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User MitI_7
Language Python (3.4.2)
Score 100
Code Size 1241 Byte
Status AC
Exec Time 152 ms
Memory 9024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 22
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 152 ms 8960 KB
sample-02.txt AC 132 ms 8916 KB
test-01.txt AC 131 ms 8904 KB
test-02.txt AC 132 ms 8912 KB
test-03.txt AC 132 ms 8944 KB
test-04.txt AC 133 ms 8896 KB
test-05.txt AC 135 ms 8900 KB
test-06.txt AC 132 ms 8896 KB
test-07.txt AC 133 ms 8888 KB
test-08.txt AC 133 ms 8912 KB
test-09.txt AC 135 ms 8960 KB
test-10.txt AC 136 ms 9024 KB
test-11.txt AC 133 ms 8888 KB
test-12.txt AC 133 ms 8964 KB
test-13.txt AC 132 ms 8896 KB
test-14.txt AC 132 ms 8904 KB
test-15.txt AC 134 ms 8996 KB
test-16.txt AC 135 ms 8920 KB
test-17.txt AC 133 ms 8928 KB
test-18.txt AC 134 ms 8916 KB
test-19.txt AC 133 ms 8916 KB
test-20.txt AC 134 ms 9016 KB