結果

問題 No.458 異なる素数の和
ユーザー kimiyuki
提出日時 2016-12-09 22:56:28
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 56 ms
コード長 960 Byte
コンパイル時間 483 ms
使用メモリ 1,616 KB
最終ジャッジ日時 2019-05-12 20:37:27

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
big1.txt AC 3 ms
1,508 KB
big2.txt AC 19 ms
1,564 KB
big3.txt AC 23 ms
1,568 KB
big4.txt AC 7 ms
1,536 KB
big5.txt AC 7 ms
1,540 KB
big6.txt AC 47 ms
1,608 KB
big7.txt AC 22 ms
1,568 KB
big8.txt AC 3 ms
1,508 KB
big9.txt AC 47 ms
1,608 KB
big10.txt AC 4 ms
1,520 KB
challenge1.txt AC 1 ms
1,488 KB
challenge2.txt AC 56 ms
1,616 KB
challenge3.txt AC 2 ms
1,504 KB
challenge4.txt AC 2 ms
1,504 KB
sample1.txt AC 3 ms
1,500 KB
sample2.txt AC 2 ms
1,496 KB
sample3.txt AC 5 ms
1,528 KB
small1.txt AC 2 ms
1,504 KB
small2.txt AC 2 ms
1,508 KB
small3.txt AC 3 ms
1,500 KB
small4.txt AC 2 ms
1,504 KB
small5.txt AC 3 ms
1,500 KB
small6.txt AC 3 ms
1,500 KB
small7.txt AC 2 ms
1,504 KB
small8.txt AC 3 ms
1,504 KB
small9.txt AC 3 ms
1,504 KB
small10.txt AC 2 ms
1,504 KB
system_test1.txt AC 20 ms
1,568 KB
system_test2.txt AC 53 ms
1,612 KB
system_test3.txt AC 3 ms
1,512 KB
system_test4.txt AC 14 ms
1,556 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <vector>
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
int main() {
    int n; cin >> n;
    vector<int> primes = sieve_of_eratosthenes(n);
    vector<int> dp(n+1, -1);
    dp[0] = 0;
    for (int p : primes) {
        repeat_reverse (i,n) if (dp[i] != -1 and i+p < n+1) {
            setmax(dp[i+p], dp[i]+1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}
0