結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2017-07-27 11:20:20 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 1,950 ms |
コンパイル使用メモリ | 157,932 KB |
実行使用メモリ | 180,608 KB |
最終ジャッジ日時 | 2024-10-10 02:04:45 |
合計ジャッジ時間 | 10,451 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
main.cpp:5:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 5 | main(){ | ^~~~ main.cpp: In function ‘int main()’: main.cpp:30:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 30 | scanf("%d",&N); | ~~~~~^~~~~~~~~
ソースコード
#include<bits/stdc++.h>int prime[20001];int p[2262];int dp[2263][20001];main(){for(int i = 2;i*i <= 20000;i++){if(prime[i])continue;for(int j = i*2;j <= 20000;j+=i){prime[j] = 1;}}int count = 0;for(int i = 2;i <= 20000;i++){if(prime[i])continue;p[count] = i;count++;}for(int i = 0;i < 2262;i++){for(int j = 0;j <= 20000;j++){dp[i+1][j] = dp[i][j];if(j < p[i])continue;if(j-p[i]==0){dp[i+1][j] = std::max(dp[i][j],1);}else if(dp[i][j-p[i]]!=0){dp[i+1][j] = std::max(dp[i][j],dp[i][j-p[i]]+1);}}}int N;scanf("%d",&N);printf("%d\n",dp[2262][N]?dp[2262][N]:-1);}