結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2023-07-28 00:31:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 913 bytes |
コンパイル時間 | 724 ms |
コンパイル使用メモリ | 74,156 KB |
実行使用メモリ | 180,096 KB |
最終ジャッジ日時 | 2024-10-05 05:28:43 |
合計ジャッジ時間 | 2,481 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<iostream>#include<algorithm>#include<vector>using namespace std;bool isPrime(int n){if(n==2)return true;for(int i=2;i<n;i++){if(n%i==0)return false;}return true;}int main(){int N;vector<int> primeNumber;cin >> N;for(int i=2;i<=N;i++){if(isPrime(i)){primeNumber.push_back(i);}}int **DP;DP = new int*[primeNumber.size()+1];for(int i=0;i<primeNumber.size()+1;i++){DP[i] = new int[N+1];}for(int i=0;i<=N;i++){DP[0][i] = 0;}DP[0][0] = 1;for(int i=0;i<primeNumber.size();i++){for(int j=0;j<=N;j++){if(j >= primeNumber[i] && DP[i][j - primeNumber[i]] > 0){DP[i+1][j] = max(DP[i][j],DP[i][j - primeNumber[i]] + 1);}else{DP[i+1][j] = DP[i][j];}}}cout << DP[primeNumber.size()][N]-1 << endl;for(int i=0;i<primeNumber.size()+1;i++){delete(DP[i]);}delete(DP);return 0;}