結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2017-05-09 10:42:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 961 bytes |
コンパイル時間 | 1,838 ms |
コンパイル使用メモリ | 171,132 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 19:59:39 |
合計ジャッジ時間 | 3,028 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;#define loop(i,a,b) for(i=a;i<b;i++)#define rloop(i,a,b) for(i=a;i>=b;i--)#define vi vector<int>#define vl vector<ll>#define vii vector< vector<int> >#define vll vector< vector<ll> >#define vs vector<string>const int inf=1000000001;const ll INF=1e16;#define MOD 1000000007#define mod 1000000009#define pi 3.14159265358979323846int main(){int n,i,j;cin>>n;vi sosuu;vi moto(n+1);loop(i,0,n+1){moto[i]=i;}moto[0]=moto[1]=-1;loop(i,2,n+1){if(moto[i]!=-1){bool flag=false;loop(j,2,sqrt(i+1)){if(i%j==0){flag=true;break;}}if(flag==false){sosuu.push_back(i);loop(j,1,n/i+1){moto[i*j]=-1;}}}}vector<int> dp(n+1,-1);dp[0]=0;loop(i,0,sosuu.size()){rloop(j,n-sosuu[i],0){if(dp[j]!=-1){dp[j+sosuu[i]]=max(dp[j+sosuu[i]],dp[j]+1);}}}cout<<dp[n]<<endl;}