結果

問題 No.458 異なる素数の和
コンテスト
ユーザー yumechi
提出日時 2016-12-23 04:40:38
言語 Ruby
(3.4.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 414 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-12-14 15:15:54
合計ジャッジ時間 66,801 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

require 'prime'

MAX_NUMBER = 20001
dp = Array.new(MAX_NUMBER, 0)
primes_list = Prime.each(MAX_NUMBER).to_a.reverse
n = gets.chomp.to_i
for i in primes_list do
    dp[i] = 1
end

for i in primes_list do
    (MAX_NUMBER-i-1).downto(i+1) do |j|
        if (j+i) >= MAX_NUMBER
            break
        elsif dp[j] > 0
            dp[j+i] = [dp[j+i], dp[j]+1].max
        end
    end
end

puts dp[n] > 0 ? dp[n] : -1
0