結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2021-05-27 23:04:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 4,854 bytes |
コンパイル時間 | 2,779 ms |
コンパイル使用メモリ | 201,252 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2024-11-06 16:51:34 |
合計ジャッジ時間 | 4,634 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
//C++#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#endif#if __cplusplus >= 201402L#include <shared_mutex>#endif#if __cplusplus >= 201703L#include <any>#include <charconv>// #include <execution>#include <filesystem>#include <optional>#include <memory_resource>#include <string_view>#include <variant>#endif#if __cplusplus > 201703L#include <barrier>#include <bit>#include <compare>#include <concepts>#if __cpp_impl_coroutine#include <coroutine>#endif#include <latch>#include <numbers>#include <ranges>#include <span>#include <stop_token>#include <semaphore>#include <source_location>#include <syncstream>#include <version>#endif//C#ifndef _GLIBCXX_NO_ASSERT#include <cassert>#endif#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#if __cplusplus >= 201103L#include <ccomplex>#include <cfenv>#include <cinttypes>#include <cstdalign>#include <cstdbool>#include <cstdint>#include <ctgmath>#include <cwchar>#include <cwctype>#endif#include<atcoder/convolution>using namespace atcoder;//#define int llusing namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;using uint = unsigned int;using pii = pair<int, int>;using pll = pair<ll, ll>;using pdd = pair<double, double>;using Graph = vector<vector<ll>>;#define rep1(i, n) for(ll i = 0; i < (int)(n); i++)#define rep2(i, a, b) for(ll i = (int)(a); i < (int)(b); i++)#define rep3(i, a, b, c) for(ll i = (int)(a); i < (int)(b); i+=(int)(c))#define rrep1(i, n) for(ll i = (int)(n); i >= 0; i--)#define rrep2(i, a, b) for(ll i = (int)(b); i >= (int)(a); i--)#define REP(i) for(ll i = 0; ; i++)#define all(v) (v).begin(), (v).end()template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }template<class T> auto min(const T& a){ return *min_element(all(a)); }template<class T> auto max(const T& a){ return *max_element(all(a)); }template<class T> ll sum(const T& a){ return accumulate(all(a), 0LL); }template<class T> ld dsum(const T& a){ return accumulate(all(a), 0.0L); }const int MOD = 1000000007;const int MMOD = 998244353;const int MAX = 510000;const ll INF = 1LL<<60;ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }ll POW(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }ll MODPOW(ll a, ll b){ ll ret = 1; while(b){ if(b & 1) ret = ret*a%MOD; a = a*a%MOD; b /= 2;} return ret;}long long fac[MAX], finv[MAX], inv[MAX];void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}bool is_prime(ll n){if(n == 1) return false;if(n == 2) return true;for(ll i = 2; i*i<=n; i++) if(n%i == 0) return false;return true;}signed main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);COMinit();ll N; cin >> N;vector<ll> P;rep1(i, 20000){if(is_prime(i+1)==true) P.push_back(i+1);}ll dp[22000] = {};rep1(i, 22000) dp[i] = -1;dp[0] = 0;for(auto p : P)rrep1(i, N){if(i-p>=0 && dp[i-p] != -1) chmax(dp[i], dp[i-p]+1);}cout << dp[N] << endl;}