結果
問題 |
No.458 異なる素数の和
|
ユーザー |
![]() |
提出日時 | 2017-07-22 05:11:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,003 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 160,856 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-09 06:16:14 |
合計ジャッジ時間 | 2,791 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; const ll INF = 1000000000000000000ll; const ll MOD = 1000000007ll; const double EPS = 1e-8; int dp[20001]; const int N = 20000; bool is_prime[N+1]; vector<long long> prime; void Eratos(){ for(int i=0; i<N; i++){ is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for(int i=2; i<=N; i++){ if(is_prime[i]){ for(int j=2; i*j<=N; j++){ is_prime[i*j] = false; } } } for(int i=2; i<=N; i++){ if(is_prime[i]){ prime.push_back(i); } } } int main(void) { //ios_base::sync_with_stdio(false); //cin.tie(0); Eratos(); int n; cin >> n; for(int i=0; i<=n; i++){ dp[i] = -1; } dp[0] = 0; for(int i=0; i<prime.size(); i++){ for(int j=n; j>=0; j--){ if(j-prime[i] >=0 && dp[j-prime[i]] >= 0){ dp[j] = max(dp[j], dp[j-prime[i]] + 1); } } } /* for(int i=0; i<=n; i++){ printf("%d ", dp[i]); } puts(""); */ cout << dp[n] << endl; return 0; }