結果

問題 No.458 異なる素数の和
コンテスト
ユーザー ikeyanabcd894
提出日時 2019-04-30 10:58:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 879 bytes
コンパイル時間 1,528 ms
コンパイル使用メモリ 162,956 KB
実行使用メモリ 180,316 KB
最終ジャッジ日時 2024-12-29 11:17:17
合計ジャッジ時間 3,606 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> p;
vector<bool> prime(20009);
int memo[2500][20009];
int INF=200000000;
int a=0;

int main(){
  cin >> N;
  for(int i=2;i<=N;i++)prime[i]=1;
  for(int i=2;i<=N;i++){
    if(prime[i]){
      p.push_back(i);
      for(int j=2*i;j<=N;j+=i){prime[j]=0;}
    }
  }
  int s=p.size();
  for(int i=0;i<=s;i++){
    for(int j=0;j<=N;j++){memo[i][j]=INF;}
  }
  memo[0][0]=0;
  for(int i=0;i<s;i++){
    for(int j=0;j<=N;j++){
      if(j<p[i]){memo[i+1][j]=memo[i][j];}
      else{
        if(memo[i][j]==INF && memo[i][j-p[i]]==INF){a++;}
        else if(memo[i][j]!=INF){memo[i+1][j]=memo[i][j];}
        else if(memo[i][j]==INF){memo[i+1][j]=memo[i][j-p[i]]+1;}
        else{memo[i+1][j]=max(memo[i][j],memo[i][j-p[i]]+1);}
      }
    }
  }
  if(memo[s][N]==INF){cout << -1 << endl;}
  else{cout << memo[s][N] << endl;}
}
0