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 |
|
|
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 |