結果
問題 | No.1267 Stop and Coin Game |
ユーザー |
|
提出日時 | 2020-10-23 22:06:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 883 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 75,624 KB |
最終ジャッジ日時 | 2025-01-15 13:05:11 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <iostream> #include <vector> using lint = long long; void solve() { int n; lint v; std::cin >> n >> v; std::vector<lint> xs(n); for (auto& x : xs) std::cin >> x; std::vector<int> dp(1 << n, -1); auto dfs = [&](auto&& f, int b, lint rem) { auto& ret = dp[b]; if (ret != -1) return ret; if (b == (1 << n) - 1) return ret = 1; ret = 0; for (int i = 0; i < n; ++i) { if ((b >> i) & 1) continue; auto nrem = rem - xs[i]; if (nrem < 0) continue; ret = std::max(ret, 2 - f(f, b | (1 << i), nrem)); } return ret; }; auto res = dfs(dfs, 0, v); std::cout << (res == 0 ? "Second" : res == 1 ? "Draw" : "First") << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }