結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2019-08-27 15:42:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 530 bytes |
コンパイル時間 | 2,239 ms |
コンパイル使用メモリ | 196,284 KB |
最終ジャッジ日時 | 2025-01-07 15:23:15 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;int main() {int n;cin>>n;bool isp[n+1];fill(isp,isp+n+1,true);isp[0]=isp[1]=false;vector<int> ps;for (int i=2;i<=n;i++) if (isp[i]) {ps.push_back(i);for (int j=i+i;j<=n;j+=i)isp[j]=false;}int dp[n+1];fill(dp,dp+n+1,-1);dp[0]=0;for (int p:ps)for (int j=n-p;j>=0;j--) if (dp[j]!=-1)dp[j+p]=max(dp[j+p],dp[j]+1);cout<<dp[n]<<endl;return 0;}