結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2020-09-23 07:12:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 380 ms / 5,000 ms |
コード長 | 933 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 75,100 KB |
実行使用メモリ | 23,040 KB |
最終ジャッジ日時 | 2024-10-01 16:39:27 |
合計ジャッジ時間 | 3,781 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #define ll long long using namespace std; vector<int> prime(int n){ vector<bool> is_prime(n+1,true); vector<int> p; for(int i=2;i <= n;i++){ if(is_prime[i]){ for(int j=2*i;j <= n;j+=i){ is_prime[j] = false; } p.push_back(i); } } return p; } vector<bool> dp(10010,false); vector<bool> calced(10010,false); bool dfs(int n){ if(n == 0 || n == 1){ return dp[n] = true; } if(n == 2 || n == 3) { return dp[n] = false; } if(calced[n]) return dp[n]; calced[n] = true; bool res = false; for(auto &x : prime(n)){ if(!dfs(n-x)){ return dp[n] = true; } } return dp[n] = false; } int main(){ int n; cin >> n; if(dfs(n)) cout << "Win" << endl; else cout << "Lose" << endl; return 0; }