結果
問題 | No.1267 Stop and Coin Game |
ユーザー |
![]() |
提出日時 | 2020-10-23 22:10:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 807 bytes |
コンパイル時間 | 1,843 ms |
コンパイル使用メモリ | 170,700 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-21 10:42:53 |
合計ジャッジ時間 | 4,187 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N; long long V; cin >> N >> V; vector<long long> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } long long S = 0; for (int i = 0; i < N; i++){ S += A[i]; } if (S <= V){ cout << "Draw" << endl; } else { vector<bool> dp(1 << N, false); for (int i = (1 << N) - 1; i >= 0; i--){ long long sum = 0; for (int j = 0; j < N; j++){ if (i >> j & 1){ sum += A[j]; } } for (int j = 0; j < N; j++){ if (!(i >> j & 1)){ if (sum + A[j] <= V && !dp[i + (1 << j)]){ dp[i] = true; break; } } } } if (dp[0]){ cout << "First" << endl; } else { cout << "Second" << endl; } } }