結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2017-05-06 01:07:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 644 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 56,832 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 15:58:50 |
合計ジャッジ時間 | 1,224 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> using namespace std; int main(int argc, const char *argv[]) { int N; cin >> N; bool primes[N + 1]; for (auto &&p : primes) p = true; primes[0] = false; primes[1] = false; for (int i = 2; i <= N; i++) { for (int j = i * 2; j <= N; j += i) { primes[j] = false; } } bool dp[N + 1] = {false}; for (int i = 2; i <= N; i++) { for (int j = 2; j <= i; j++) { if (primes[j]) { if (i - j >= 2 && !dp[i - j]) { dp[i] = true; break; } } } } // for (int i = 2; i <= N; i++) { // cout << i << ":" << dp[i] << endl; // } cout << (dp[N] ? "Win" : "Lose") << endl; return 0; }