結果

問題 No.458 異なる素数の和
ユーザー ikeyanabcd894ikeyanabcd894
提出日時 2019-04-30 10:58:23
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 879 bytes
コンパイル時間 1,448 ms
コンパイル使用メモリ 148,632 KB
実行使用メモリ 180,328 KB
最終ジャッジ日時 2023-08-28 12:25:52
合計ジャッジ時間 3,348 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,596 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 16 ms
51,108 KB
testcase_04 AC 19 ms
57,256 KB
testcase_05 AC 101 ms
162,920 KB
testcase_06 WA -
testcase_07 AC 3 ms
11,744 KB
testcase_08 AC 99 ms
163,844 KB
testcase_09 AC 9 ms
30,328 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 114 ms
180,328 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 11 ms
38,636 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 6 ms
22,140 KB
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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