結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2021-09-05 19:35:22 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 982 bytes |
コンパイル時間 | 5,619 ms |
コンパイル使用メモリ | 142,808 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 18:59:02 |
合計ジャッジ時間 | 5,952 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream>#include <utility>#include <vector>#include <string>#include <cmath>#include <algorithm>#include <functional>#include <iomanip>#include <map>#include <set>#include <queue>using namespace std;using ll = long long int;#define chmax(x,y) (x) = ((x) > (y)) ? (x) : ((x) = (y));#define chmin(x,y) (x) = ((x) < (y)) ? (x) : ((x) = (y));int main(int argc, char const *argv[]){int N; cin >> N;vector<int> prime;auto eratos = [&](int x){vector<int> v(x+1,1);v[0] = v[1] = 0;for(int i=2;i*i<=x;++i){if(v[i]){//std::cout << i << std::endl;for(int j=i*i;j<=x;j+=i){v[j] = 0;}}}for(int i=2;i<=x;++i){if(v[i])prime.push_back(i);}};eratos(N);vector<int> dp(N+2,-1);dp[0] = 0;for(auto &p : prime)for(int i=N;i>=0;--i){if(dp[i] != -1 && i+p <= N)chmax(dp[i+p],dp[i]+1);}std::cout << dp[N] << std::endl;}