結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2019-02-01 00:03:28 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 3,222 ms |
コンパイル使用メモリ | 62,204 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-04 22:59:57 |
合計ジャッジ時間 | 3,762 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import sequtils,mathproc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}proc scan(): int =while true:let k = getchar_unlocked()if k < '0': returnresult = 10 * result + k.ord - '0'.ordproc getIsPrimes(n:int) :seq[bool] = # [0...n] O(n loglog n)result = newSeqWith(n+1,true)result[0] = falseresult[1] = falsefor i in 2..n.float.sqrt.int :if not result[i]: continuefor j in countup(i*2,n,i):result[j] = falselet m = scan()let n = scan()let C = newSeqWith(n,scan())var dp = newSeq[int](m)proc impl(n,x:int) =for c in C:if x-c <= 1 : continueif dp[x-c] >= n + 1 : continuedp[x-c] = n + 1impl(n+1,x-c)impl(0,m)const isPrimes = getIsPrimes(10001)var ans = 0for i in 2..<m:if not isPrimes[i] : continueif dp[i] == 0 : continueans += dp[i]let plus = m div C.min()echo ans + plus