結果
問題 |
No.458 異なる素数の和
|
ユーザー |
![]() |
提出日時 | 2017-12-16 15:51:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 918 bytes |
コンパイル時間 | 610 ms |
コンパイル使用メモリ | 73,568 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-14 19:23:50 |
合計ジャッジ時間 | 5,664 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | AC * 1 RE * 27 |
ソースコード
#include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; int N; int isprime[20010]; int dp[20010]; void eratos(int m) { for (int i = 0; i <= m; i++) isprime[i] = true; isprime[0] = isprime[1] = false; for (int i = 2; i <= m; ++i) { if (isprime[i]) { for (int j = 2 * i; j <= m; j += i) isprime[j] = false; } } } int main() { cin >> N; eratos(N); vector<int> primes; for (int i = 2; i < N + 1; i++) { if (isprime[i]) primes.push_back(i); } memset(dp, -1, sizeof(dp)); dp[0] = 0; for (auto p : primes) { for (int i = N; i >= 0; i++) { if (i - p < 0 || dp[i - p] < 0) continue; dp[i] = max(dp[i], dp[i - p] + 1); } } cout << dp[N] << endl; return 0; }