結果
問題 | No.458 異なる素数の和 |
ユーザー | kotatsuinu5 |
提出日時 | 2020-11-28 17:57:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,199 ms / 2,000 ms |
コード長 | 848 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 87,008 KB |
実行使用メモリ | 430,328 KB |
最終ジャッジ日時 | 2023-10-10 00:49:04 |
合計ジャッジ時間 | 11,233 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 89 ms
76,128 KB |
testcase_01 | AC | 428 ms
177,480 KB |
testcase_02 | AC | 527 ms
205,388 KB |
testcase_03 | AC | 162 ms
90,396 KB |
testcase_04 | AC | 193 ms
106,072 KB |
testcase_05 | AC | 1,038 ms
371,344 KB |
testcase_06 | AC | 775 ms
201,636 KB |
testcase_07 | AC | 93 ms
76,160 KB |
testcase_08 | AC | 1,002 ms
374,336 KB |
testcase_09 | AC | 120 ms
83,928 KB |
testcase_10 | AC | 78 ms
71,220 KB |
testcase_11 | AC | 1,199 ms
430,328 KB |
testcase_12 | AC | 213 ms
71,304 KB |
testcase_13 | AC | 79 ms
71,364 KB |
testcase_14 | AC | 80 ms
70,964 KB |
testcase_15 | AC | 79 ms
71,116 KB |
testcase_16 | AC | 140 ms
89,920 KB |
testcase_17 | AC | 83 ms
76,148 KB |
testcase_18 | AC | 81 ms
75,744 KB |
testcase_19 | AC | 78 ms
71,108 KB |
testcase_20 | AC | 85 ms
76,000 KB |
testcase_21 | AC | 78 ms
71,340 KB |
testcase_22 | AC | 77 ms
70,944 KB |
testcase_23 | AC | 87 ms
75,892 KB |
testcase_24 | AC | 85 ms
75,968 KB |
testcase_25 | AC | 80 ms
73,996 KB |
testcase_26 | AC | 81 ms
75,936 KB |
testcase_27 | AC | 474 ms
182,196 KB |
testcase_28 | AC | 1,155 ms
423,484 KB |
testcase_29 | AC | 103 ms
76,408 KB |
testcase_30 | AC | 324 ms
136,448 KB |
ソースコード
import math N=int(input()) S=[] maxv=N+10 def eratos(n): isprime=[True]*(n+1) isprime[0]=False isprime[1]=False for i in range(2,int(math.sqrt(n))+1): if isprime[i]==True: j=i+i while j<=n: isprime[j] =False j=j+i for i in range(n+1): if isprime[i]==True: S.append(i) return S sosu=eratos(N) #print(sosu) #print(len(sosu)) DP = [[-1]*(maxv) for i in range(len(S)+1)] for i in range(len(S)+1): DP[i][0]=0 for i in range(len(S)): for j in range(maxv): if j+S[i]<=N and DP[i][j]!=-1: DP[i+1][j+S[i]]=DP[i][j]+1 DP[i+1][j]=max(DP[i][j],DP[i+1][j]) ans=-1 for i in range(len(S)+1): if DP[i][N]>ans: ans=DP[i][N] if ans>0: print(ans) else: print(-1) #print(DP)