結果
問題 |
No.458 異なる素数の和
|
ユーザー |
![]() |
提出日時 | 2018-02-13 01:10:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 900 bytes |
コンパイル時間 | 1,449 ms |
コンパイル使用メモリ | 166,668 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-27 06:01:08 |
合計ジャッジ時間 | 3,867 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 12 WA * 16 |
ソースコード
#include<bits/stdc++.h> using namespace std; int N, dp[40030]; bool prime[20010]; int main(){ for(int i=0;i<40030;i++){ dp[i]=-1; } for(int i=0;i<20010;i++){ prime[i]=true; } prime[1]=true; for(int i=2;i<=sqrt(20010);i++){ if(!prime[i]){ continue; } for(int j=i+i;j<20010;j+=i){ prime[j]=false; } } cin>>N; dp[0]=0; for(int p=1;p<20010;p++){ if(!prime[p]){ continue; } for(int i=20010;i>=0;i--){ if(dp[i]!=(-1)){ dp[i+p]=max(dp[i+p], dp[i]+1); } } } cout<<dp[N]<<endl; return 0; }