結果
問題 |
No.1267 Stop and Coin Game
|
ユーザー |
|
提出日時 | 2020-10-24 02:02:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 987 bytes |
コンパイル時間 | 1,270 ms |
コンパイル使用メモリ | 115,604 KB |
最終ジャッジ日時 | 2025-01-15 14:51:32 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <algorithm> #include <cmath> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <tuple> #include <vector> using namespace std; using ll = int64_t; #define rep(i, j, n) for (int i = j; i < (n); ++i) #define rrep(i, j, n) for (int i = (n)-1; j <= i; --i) ll n, v; bool seen[1 << 20]; bool dfs(int S, vector<ll>& a, vector<bool>& dp) { if (seen[S]) return dp[S]; seen[S] = true; ll s = 0; rep(i, 0, n) if (S >> i & 1) s += a[i]; if (s > v) return dp[S] = true; bool res = false; rep(i, 0, n) if ((S >> i & 1) == 0) res |= !dfs(S | 1 << i, a, dp); return dp[S] = res; } int main() { cin >> n >> v; vector<ll> a(n); ll s = 0; rep(i, 0, n) { cin >> a[i]; s += a[i]; } if (s <= v) { cout << "Draw" << endl; return 0; } vector<bool> dp(1 << n); if (dfs(0, a, dp)) cout << "First" << endl; else cout << "Second" << endl; return 0; }