Submission #2238270


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define erep(i,a,b) for(int i=a;i<=(int)(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>(a);i--)
#define eper(i,a,b) for(int i=((int)(a));i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
using namespace std;
typedef long long ll;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int board[3][3], b[3][3], c[3][3], sum;

int solve(int depth) {
    if (depth == 9) {
        int ans = 0;
        rep(i, 0, 2) rep(j, 0, 3) 
            if (board[i][j] == board[i+1][j]) 
                ans += b[i][j];
        rep(i, 0, 3) rep(j, 0, 2) 
            if (board[i][j] == board[i][j+1]) 
                ans += c[i][j];
        return ans;
    }
    int s = 0, t = INF;
    rep(i, 0, 3) {
        rep(j, 0, 3) {
            if (board[i][j] == 1 || board[i][j] == -1) continue;
            if (depth%2) {
                board[i][j] = -1;
                t = min(t, solve(depth+1));
                board[i][j] = 0;
            } else {
                board[i][j] = 1;
                s = max(s, solve(depth+1));
                board[i][j] = 0;
            }
        }
    }
    return depth%2 ? t : s;
}
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    rep(i, 0, 2) rep(j, 0, 3) {
        cin >> b[i][j];
        sum += b[i][j];
    }
    rep(i, 0, 3) rep(j, 0, 2) {
        cin >> c[i][j];
        sum += c[i][j];
    }
    int ans = solve(0);
    printf("%d\n", ans);
    printf("%d\n", sum-ans);
    return 0;
}

Submission Info

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