#312800 (Nim) No.458 異なる素数の和

提出ソース

結果

問題	No.458 異なる素数の和
ユーザー	むらため
提出日時	2019-01-26 12:05:12
言語	Nim (2.0.2)
結果	AC
実行時間	93 ms / 2,000 ms
コード長	900 bytes
コンパイル時間	2,212 ms
コンパイル使用メモリ	66,696 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-14 02:54:56
合計ジャッジ時間	4,010 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	27 ms 4,376 KB
testcase_02	AC	36 ms 4,376 KB
testcase_03	AC	8 ms 4,376 KB
testcase_04	AC	9 ms 4,376 KB
testcase_05	AC	79 ms 4,380 KB
testcase_06	AC	34 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	78 ms 4,380 KB
testcase_09	AC	4 ms 4,380 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	90 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	5 ms 4,376 KB
testcase_17	AC	2 ms 4,376 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	2 ms 4,380 KB
testcase_22	AC	2 ms 4,376 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	2 ms 4,376 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	32 ms 4,376 KB
testcase_28	AC	93 ms 4,376 KB
testcase_29	AC	3 ms 4,376 KB
testcase_30	AC	21 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sequtils,math
template `max=`*(x,y) = x = max(x,y)

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': break
    result = 10 * result + k.ord - '0'.ord

proc getIsPrimes(n:int) :seq[bool] = # [0...n] O(n loglog n)
  result = newSeqWith(n+1,true)
  result[0] = false
  result[1] = false
  for i in 2..n.float.sqrt.int :
    if not result[i]: continue
    for j in countup(i*2,n,i):
      result[j] = false
proc getPrimes(n:int):seq[int] = # [2,3,5,...n]
  let isPrimes = getIsPrimes(n)
  result = @[]
  for i,p in isPrimes:
    if p : result &= i


const primes = getPrimes(20010)
var dp: array[20010,int]
let n = scan()
for p in primes:
  for i in (n-p).countdown(2):
    if dp[i] == 0 : continue
    dp[i+p] .max= dp[i] + 1
  dp[p] .max= 1

if dp[n] == 0 : echo -1
else: echo dp[n]

yukicoder

結果

テストケース

ソースコード