結果
問題 | No.458 異なる素数の和 |
ユーザー | yuppe19 😺 |
提出日時 | 2016-12-09 00:24:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 997 bytes |
コンパイル時間 | 1,170 ms |
コンパイル使用メモリ | 52,748 KB |
最終ジャッジ日時 | 2023-08-19 02:39:32 |
合計ジャッジ時間 | 1,661 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge14 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:8:1: error: ‘vector’ does not name a type; did you mean ‘perror’? vector<int> primes; ^~~~~~ perror main.cpp:9:1: error: ‘vector’ does not name a type; did you mean ‘perror’? vector<vector<int>> dp; ^~~~~~ perror main.cpp: In function ‘int rec(int, int)’: main.cpp:14:14: error: ‘dp’ was not declared in this scope int &res = dp[i][acc]; ^~ main.cpp:21:12: error: ‘primes’ was not declared in this scope if(acc + primes[i] <= n) { ^~~~~~ main.cpp:21:12: note: suggested alternative: ‘res’ if(acc + primes[i] <= n) { ^~~~~~ res main.cpp: In function ‘int main()’: main.cpp:30:3: error: ‘vector’ was not declared in this scope vector<bool> is_prime(n+1, true); ^~~~~~ main.cpp:30:3: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’? main.cpp:3:1: +#include <vector> using namespace std; main.cpp:30:3: vector<bool> is_prime(n+1, true); ^~~~~~ main.cpp:30:10: error: expected primary-expression before ‘bool’ vector<bool> is_prime(n+1, true); ^~~~ main.cpp:31:3: error: ‘is_prime’ was not declared in this scope is_prime[0] = is_prime[1] = false; ^~~~~~~~ main.cpp:31:3: note: suggested alternative: ‘iswprint’ is_prime[0] = is_prime[1] = false; ^~~~~~~~ iswprint main.cpp:32:12: error: ‘sqrt’ was not declared in this scope int sq = sqrt(n); ^~~~ main.cpp:32:12: note: suggested alternative: ‘sq’ int sq = sqrt(n); ^~~~ sq main.cpp:41:23: error: ‘primes’ was not declared in this scope if(is_prime[i]) { primes.push_back(i); } ^~~~~~ main.cpp:41:23: note: suggested alternative: ‘stime’ if(is_prime[i]) { primes.push_back(i); } ^~~~~~ stime main.cpp:43:7: error: ‘primes’ was not declared in this scope m = primes.size(); ^~~~~~ m
ソースコード
#include <iostream> #include <algorithm> using namespace std; using i64 = long long; int n; constexpr int inf = 987654321; vector<int> primes; vector<vector<int>> dp; int m; // i番目を見てる。今までの和は acc int rec(int i, int acc) { int &res = dp[i][acc]; if(res != -1) { return res; } if(i == m) { if(acc == n) { return res = 0; } return res = -inf; } res = rec(i+1, acc); if(acc + primes[i] <= n) { res = max(res, rec(i+1, acc+primes[i]) + 1); } return res; } int main(void) { scanf("%d", &n); vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false; int sq = sqrt(n); for(int i=2; i<=sq; ++i) { if(is_prime[i]) { for(int j=i*i; j<=n; j+=i) { is_prime[j] = false; } } } for(int i=2; i<=n; ++i) { if(is_prime[i]) { primes.push_back(i); } } m = primes.size(); dp.assign(m+1, vector<int>(n+1, -1)); int res = rec(0, 0); if(res < 0) { res = -1; } printf("%d\n", res); return 0; }