結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2021-08-23 04:55:21 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 7,070 ms |
コンパイル使用メモリ | 143,452 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 04:27:32 |
合計ジャッジ時間 | 7,011 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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;int main(int argc, char const *argv[]){int N; cin >> N;bool _prime[20010];auto _era = [&](){for(int i=0;i<=20010;++i)_prime[i] = true;_prime[0] = _prime[1] = false;for(int i=2;i*i <= 20010;++i){if(_prime[i]){for(int j=i*i;j<=20010; j += i){_prime[j] = false;}}}};_era();vector<int> primes;for(int i=0;i<=N;++i)if(_prime[i])primes.emplace_back(i);vector<int> dp(N+1,-1);dp[0] = 0;auto chmax = [](int &x, int y){if(x < y)x = y;return x;};for(auto &pri : primes){for(int j=N;j>=0;--j){if(dp[j] != -1 && j + pri <= N){chmax(dp[j+pri] , dp[j] + 1);}}}std::cout << dp[N] << std::endl;}