結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2020-06-08 06:26:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 706 bytes |
コンパイル時間 | 873 ms |
コンパイル使用メモリ | 85,720 KB |
最終ジャッジ日時 | 2025-01-11 00:06:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <set> #include <string> #include <map> #include <numeric> using namespace std; typedef long long int ll; int dp[10001]; bool is_not_prime[10001]; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; dp[2]=dp[3]=0; vector<int> p; for(int i=2;i<=n;i++){ if(!is_not_prime[i]){ p.push_back(i); for(int j=i+i;j<=n;j+=i){ is_not_prime[j]=1; } } } for(int i=4;i<=n;i++){ bool ok=0; for(int j=0;j<p.size();j++){ if(i-p[j]>=2){ if(!dp[i-p[j]]){ ok=1; } }else break; } if(ok)dp[i]=1; } if(!dp[n]){ printf("Lose\n"); } else{ printf("Win\n"); } }