結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2017-11-03 01:11:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 1,359 ms |
コンパイル使用メモリ | 91,468 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-22 14:25:19 |
合計ジャッジ時間 | 2,879 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<ctime>#include<cctype>#include<climits>#include<iostream>#include<string>#include<vector>#include<map>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<memory>#include<functional>#include<set>using namespace std;#define ALL(g) (g).begin(),(g).end()#define REP(i, x, n) for(int i = x; i < n; i++)#define rep(i,n) REP(i,0,n)#define F(i,j,k) fill(i[0],i[0]+j*j,k)#define P(p) cout<<(p)<<endl;#define INF 1<<25typedef long long ll;int dy[8]={1,1,1,0,0,-1,-1,-1};int dx[8]={-1,0,1,-1,1,-1,0,1};struct S{int a,b,c;};bool asc(const S& left,const S& right){return left.c > right.c;}int N,isprime[20001];vector<int>prime;void eratos(int m){for (int i = 0; i <= m; ++i) isprime[i] = true;isprime[0] = isprime[1] = false;for (int i = 2; i <= m; ++i){if(isprime[i]){for (int j = 2 * i; j <= m; j += i){isprime[j] = false;}}}for (int i = 2; i <= m; ++i)if(isprime[i])prime.push_back(i);}int main(void){cin >> N;vector<int>dp(N+1,-1);eratos(20000);dp[0] = 0;for(auto i : prime){for (int j = N; j >= 0; --j){if(i+j<=N && dp[j]!=-1){dp[i+j]=max(dp[i+j], dp[j] + 1);}}if(i>=N)break;}cout<<dp[N]<<endl;return 0;}