結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2024-01-09 14:43:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,480 bytes |
コンパイル時間 | 1,969 ms |
コンパイル使用メモリ | 196,516 KB |
最終ジャッジ日時 | 2025-02-18 16:44:38 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void printv(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}int64_t rand64(){int64_t l = rand();int64_t r = rand();return (l<<31)+r;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}bool yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;return b;}bool debug;bool randomInput;bool debugOutput;int numOfTestCase;using ans_type = int;int N;void input(){if(numOfTestCase > 1){}if(randomInput){}else{cin >> N;}return;}void output_input(){;}ans_type calc(){vector<int> P = {2};for(int i = 3; i <= N; i++){bool b = true;for(auto p : P){if(i%p == 0) {b = false;break;}if(p*p > i) break;}if(b) P.push_back(i);}int INF = 1001002003;vector<int> dp(N+1, -INF);dp[0] = 0;for(auto p : P){for(int i = N; i-p >= 0; i--){chmax(dp[i], dp[i-p]+1);}}int ans = dp[N];if(ans < 0) ans = -1;cout << ans << endl;return ans_type();}ans_type calc_simple(){return ans_type();}void output(ans_type ans){return;}int main(){debug = 0;randomInput = 0;debugOutput = 0;numOfTestCase = 1;srand(time(NULL));cout << fixed << setprecision(12);if(numOfTestCase == 0) cin >> numOfTestCase;if(debug){for(int i = 0; i < numOfTestCase; i++){if(debugOutput) cout << string(16, '-') << endl;input();ans_type ans = calc();ans_type ansSimple = calc_simple();if(ans != ansSimple){output_input();output(ans);output(ansSimple);}}}else{for(int i = 0; i < numOfTestCase; i++){input();output(calc());}}return 0;}