結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2019-03-20 22:03:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,789 bytes |
コンパイル時間 | 921 ms |
コンパイル使用メモリ | 109,184 KB |
最終ジャッジ日時 | 2025-01-06 23:38:18 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream>#include <iomanip>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <string>#include <sstream>#include <complex>#include <vector>#include <list>#include <queue>#include <deque>#include <stack>#include <map>#include <set>#define rep(i, n) for (int i = 0; i < (n); i++)#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)#define reps(i, n) for (int i = 1; i <= (n); i++)#define repi(i, a, b) for (int i = (a); i < (b); i++)#define all(a) (a).begin(), (a).end()#define bit(b) (1ull << (b))using namespace std;using i32 = long long;using u32 = unsigned long long;using i64 = long long;using u64 = unsigned long long;using f64 = double;using vi32 = vector<i32>;using vu32 = vector<u32>;using vi64 = vector<i64>;using vu64 = vector<u64>;using vf64 = vector<f64>;using vstr = vector<string>;using vvi32 = vector<vi32>;using vvu32 = vector<vu32>;using vvi64 = vector<vi64>;using vvu64 = vector<vu64>;using vvf64 = vector<vf64>;template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }i64 dp[20010];int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(16);vi32 primes;for (int i = 2; i <= 20000; i++) {bool flag = true;for (int j = 2; j * j <= i; j++) {if (i % j == 0) flag = false;}if (flag) primes.push_back(i);}int n;cin >> n;rep(i, 20010) dp[i] = -1e9;dp[0] = 0;rep(j, primes.size()) {rrep(i, 20000) {if (i + primes[j] > 20000) continue;if (dp[i] < 0) continue;amax(dp[i + primes[j]], dp[i] + 1);}}if (dp[n] < 0) cout << -1 << endl;else cout << dp[n] << endl;return 0;}