結果

問題 No.458 異なる素数の和
ユーザー atommy-euph
提出日時 2025-02-18 22:07:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,206 bytes
コンパイル時間 1,998 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 418,176 KB
最終ジャッジ日時 2025-02-18 22:07:28
合計ジャッジ時間 8,274 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
is_prime = [1 for _ in range(N+1)]
is_prime[0] = 0; is_prime[1] = 0
for i in range(2, N+1):
    if not is_prime[i]: continue
    for j in range(i*2, N+1, i): is_prime[j] = 0

primes = [i for i in range(len(is_prime)) if is_prime[i]]
C = len(primes)

dp = [[-1] * (N+1) for _ in range(C+1)]
for i in range(C+1):
    dp[i][0] = 0
w = N
for i in range(C-1, -1, -1):
    for w in range(N+1):
        if w - primes[i] < 0: continue

        use = dp[i+1][w-primes[i]]
        dp[i][w] = max(
            use + 1,
            dp[i+1][w]
        )

print(dp[0][N] if dp[0][N] > 0 else -1)      


# DFS
# import sys
# sys.setrecursionlimit(1010101)

# dp = [[-1] * (N+1) for _ in range(C+1)]
# def dfs(i, w): # w を i~C-1番目の素数の和で表すことができる場合、その中での最大の和の回数を返す
#     if dp[i][w] > -1: 
#         return dp[i][w]
#     res = 0
#     if i == C or w < 0:
#         return -1
#     if w == 0:
#         return 0
    
#     res =  dfs(i+1, w)
#     use = -1
#     if w-primes[i] >= 0:
#         use = dfs(i+1, w-primes[i]) 
#     if use != -1:
#         res = max(res, use + 1)
#     dp[i][w] = res

#     return res


# print(dfs(0, N))
0