結果

問題 No.458 異なる素数の和
コンテスト
ユーザー MitI_7
提出日時 2018-02-15 11:40:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 2,151 bytes
コンパイル時間 2,323 ms
コンパイル使用メモリ 172,628 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-25 23:04:29
合計ジャッジ時間 3,672 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define LL long long
#define VI vector<int>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }

// 4近傍（右, 下, 左, 上）
const std::vector<int> dy = { 0, -1, 0, 1 };
const std::vector<int> dx = { 1, 0, -1, 0 };

using namespace std;

// nまでの素数のリストを作成(nを含む) O(N log log N)
vector<int> make_prime_list(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;

    vector<int> prime_list;
    for (int i = 2; i < n + 1; ++i) {
        if (!is_prime[i]) { continue; }
        prime_list.emplace_back(i);

        for (int j = i + i; j < n + 1; j += i) {
            is_prime[j] = false;
        }
    }
    return prime_list;  // 素数のリスト
    //return is_prime;  // すべての数値について素数かどうか
}

int main() {
    int N;
    cin >> N;

    vector<int> prime_list = make_prime_list(N);

    vector<int> dp(N + 1, -1);

    FOE(p, prime_list) {
        dp[p] = 1;
    }

    for(int i = dp.size() - 1; i >= 0; --i) {
        if (dp[i] == -1) { continue; }

        for(int j = dp.size() - 1; j > i ; --j) {
            if (dp[j] == -1) { continue; }

            if (i + j < dp.size()) {
                dp[i + j] = max(dp[i + j], dp[i] + dp[j]);
            }
        }
    }

    cout << dp[N] << endl;

    return 0;
}
0