結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2018-08-18 11:36:28 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 873 bytes |
コンパイル時間 | 674 ms |
コンパイル使用メモリ | 62,980 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 13:43:12 |
合計ジャッジ時間 | 2,092 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <utility>using namespace std;typedef long long ll;typedef pair<int, int> P;const int INF = (int)1e9 + 1;bool is_prime[20010];int dp[20010];void eratos(int m) {for (int i = 0; i <= m; i++) {is_prime[i] = true;}is_prime[0] = is_prime[1] = false;for (int i = 2; i <= m; i++) {if (is_prime[i]) {for (int j = 2 * i; j <= m; j += i) {is_prime[j] = false;}}}return;}int main() {int n;cin >> n;for (int i = 0; i <= n; i++) {dp[i] = -1;}eratos(n);vector<int> prime;for (int i = 2; i < 20001; i++) {if (is_prime[i]) {prime.push_back(i);}}dp[0] = 0;for (auto u : prime) {for (int j = n; j >= 0; j--) {if (u + j <= n && dp[j] != -1) {dp[u + j] = max(dp[u + j], dp[j] + 1);}}}cout << dp[n] << endl;return 0;}