結果
問題 | No.458 異なる素数の和 |
ユーザー | seaesae |
提出日時 | 2018-11-14 23:19:36 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,713 bytes |
コンパイル時間 | 428 ms |
コンパイル使用メモリ | 60,044 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-06 20:05:44 |
合計ジャッジ時間 | 1,779 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 19 ms
5,376 KB |
testcase_02 | AC | 22 ms
5,376 KB |
testcase_03 | AC | 8 ms
5,376 KB |
testcase_04 | AC | 10 ms
5,376 KB |
testcase_05 | AC | 34 ms
5,376 KB |
testcase_06 | AC | 22 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 35 ms
5,376 KB |
testcase_09 | AC | 5 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 39 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 7 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 22 ms
5,376 KB |
testcase_28 | AC | 40 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 16 ms
5,376 KB |
ソースコード
//yukicoderN0.458「異なる素数の和」 //Nを異なる素数の和で表せるとき、その中での最大の和の回数M //表せない場合-1を出力 #include<iostream> #include<vector> using namespace std; int N; bool isprime[20010]; //エラトステネスのふるい void eratos(int m){ for(int i=0; i<=m; i++)isprime[i]=true; isprime[0]=isprime[1]=false; //iを残してiの倍数を消していく for(int i=2; i<=m; i++){ if(isprime[i]){//ある数が素数のとき、その倍数は全て素数ではない for(int j=2*i; j<=m; j+=i){ isprime[j]=false; } } } } vector<int> prime; int dp[20010]; int main(){ cin>>N; //Nが異なる素数の和で表せるとき、N-Aは異なる素数の和で表せる(Aは素数) //dp[i]:iまでの数を見たときの素数の和の数の最大値 //ただし、同じ素数を使うことは出来ない //dp初期状態dp[i]=-1 for(int i=0; i<=N; i++)dp[i]=-1; eratos(20010); for(int i=2; i<20001; i++) if(isprime[i])prime.push_back(i); dp[0]=0; //小さい素数から順番に使っても題意は変わらないので素数でループを回す //同じ素数は使えないのでauto u:primeを使う(素数のループ) for(auto u:prime)//uにはprimeの各要素を自動で代入してprimeの要素の回数ループ for(int j=N; j>=0; j--) if(u+j<=N && dp[j]!=-1)//u+jがNを超えなく、(dp[]の範囲) dp[u+j]=max(dp[u+j],dp[j]+1);//既存の数字に対してuを追加した数が一つ増える cout<<dp[N]<<endl; return 0; }