結果
問題 | No.458 異なる素数の和 |
ユーザー |
|
提出日時 | 2022-08-04 00:33:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,276 ms / 2,000 ms |
コード長 | 619 bytes |
コンパイル時間 | 415 ms |
コンパイル使用メモリ | 81,788 KB |
実行使用メモリ | 417,408 KB |
最終ジャッジ日時 | 2024-09-13 18:59:31 |
合計ジャッジ時間 | 10,021 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N = int(input())# dp[i][j] = i こめの素数までを使って j を作るときの素数の個数の最大値is_sosu = [True]*(N+10)is_sosu[0] = is_sosu[1] = Falsesosu = []for i in range(N+1):if is_sosu[i]:sosu.append(i)for j in range(i*2, N+1, i):is_sosu[j] = Falsedp = [[-10**10]*(N+1) for _ in range(len(sosu)+1)]dp[-1][0] = 0for i in range(len(sosu)):for j in range(N+1):dp[i][j] = dp[i-1][j]if j >= sosu[i]:dp[i][j] = max(dp[i][j], dp[i-1][j-sosu[i]]+1)ans = dp[len(sosu)-1][N]if ans < 0:print(-1)else:print(ans)