結果
問題 | No.102 トランプを奪え |
ユーザー | pekempey |
提出日時 | 2015-08-20 13:03:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 224 ms / 5,000 ms |
コード長 | 1,352 bytes |
コンパイル時間 | 1,559 ms |
コンパイル使用メモリ | 163,652 KB |
実行使用メモリ | 8,936 KB |
最終ジャッジ日時 | 2023-09-25 13:47:33 |
合計ジャッジ時間 | 2,936 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 17 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 44 ms
4,684 KB |
testcase_06 | AC | 46 ms
5,008 KB |
testcase_07 | AC | 13 ms
4,380 KB |
testcase_08 | AC | 62 ms
5,192 KB |
testcase_09 | AC | 224 ms
8,936 KB |
testcase_10 | AC | 220 ms
8,692 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, a) for (int i = 0; i < (a); i++) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) for (int i = (a) - 1; i >= 0; i--) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; const ll inf = 1e9; const ll mod = 1e9 + 9; typedef pair<int, int> P; map<pair<P, vector<int>>, P> dp; P dfs(P score, vector<int> N) { sort(N.begin(), N.end()); auto key = make_pair(score, N); if (dp.count(key)) return dp[key]; swap(score.first, score.second); if (all_of(N.begin(), N.end(), [](int x) { return x == 0; })) { return score; } P res(-1, inf); rep (j, 4) { rep2 (k, 1, min(4, N[j] + 1)) { N[j] -= k; P p; if (k < N[j]) { p = dfs(P(score.first + k, score.second), N); } else { p = dfs(P(score.first + (score.second + 1) / 2 + k, score.second / 2), N); } swap(p.first, p.second); if (res.first < p.first) { res = p; } else if (res.first == p.first && res.second > p.second) { res = p; } N[j] += k; } } return dp[key] = res; } int main() { vector<int> N(4); rep (i, 4) cin >> N[i]; auto ans = dfs(P(0, 0), N); if (ans.first > ans.second) { cout << "Taro" << endl; } else if (ans.first == ans.second) { cout << "Draw" << endl; } else { cout << "Jiro" << endl; } return 0; }