結果

問題 No.458 異なる素数の和
ユーザー vjudge1
提出日時 2025-07-27 14:08:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 529 bytes
コンパイル時間 2,098 ms
コンパイル使用メモリ 192,096 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-27 14:08:45
合計ジャッジ時間 3,657 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 20007;
const int inf=1e18;
int n,f[N],pr[N],tot=0;
bool vis[N];
signed main(){
	cin >> n;
	vis[0]=vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i])pr[++tot]=i;
		for(int j=1;j<=tot&&pr[j]*i<=n;j++){
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	for(int i=1;i<=n;i++)f[i]=-inf;
    for(int i=1;i<=tot;i++)
        for (int j=n;j>= 0;j--) 
            if (pr[i]+j<=n)f[pr[i]+j]=max(f[pr[i]+j],f[j]+1);
    cout<<(f[n]<0?-1:f[n]);
}
0