結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2020-08-31 07:28:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 5,000 ms |
コード長 | 549 bytes |
コンパイル時間 | 786 ms |
コンパイル使用メモリ | 72,688 KB |
最終ジャッジ日時 | 2025-01-14 02:17:38 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> using namespace std; int main(){ int N; cin >> N; vector<bool> prime(N + 1, true); prime[0] = false; prime[1] = false; for (int i = 2; i <= N; i++){ if (prime[i]){ for (int j = i * 2; j <= N; j += i){ prime[j] = false; } } } vector<bool> dp(N + 1, false); dp[0] = true; dp[1] = true; for (int i = 2; i <= N; i++){ for (int j = 0; j <= i; j++){ if (prime[j] && !dp[i - j]){ dp[i] = true; } } } if (dp[N]){ cout << "Win" << endl; } else { cout << "Lose" << endl; } }