結果

問題 No.458 異なる素数の和
コンテスト
ユーザー joji
提出日時 2026-01-21 00:31:54
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 644 ms / 2,000 ms
コード長 1,002 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,245 ms
コンパイル使用メモリ 337,476 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-21 00:32:03
合計ジャッジ時間 8,422 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

void solve() {
        int N;
        cin >> N;
        vector<int> primes;
        for (int i = 2; i <= N; i++) {
                int cnt = 0;
                for (int j = 1; j <= i; j++) {
                        if (i % j == 0) {
                                cnt++;
                        }
                }
                if (cnt == 2) {
                        primes.push_back(i);
                }
        }
        vector<int> dp(N + 1, -1);
        dp[0] = 0;
        for (auto &prime : primes) {
                for (int i = N; i >= prime; i--) {
                        if (i - prime >= 0 && dp[i - prime] != -1) {
                                dp[i] = max(dp[i], dp[i - prime] + 1);
                        }
                }
        }
        cout << dp[N] << '\n';
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}
0