結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2016-07-01 22:41:07 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-10-04 22:23:33 |
合計ジャッジ時間 | 2,108 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
M = int(input())N = int(input())Cs = list(map(int, input().split()))def primes2(limit):''' returns a list of prime numbers upto limit.source: Rossetta code: Sieve of Eratostheneshttp://rosettacode.org/wiki/Sieve_of_Eratosthenes#Odds-only_version_of_the_array_sieve_above'''if limit < 2: return []if limit < 3: return [2]lmtbf = (limit - 3) // 2buf = [True] * (lmtbf + 1)for i in range((int(limit ** 0.5) - 3) // 2 + 1):if buf[i]:p = i + i + 3s = p * (i + 1) + ibuf[s::p] = [False] * ((lmtbf - s) // p + 1)return [2] + [i + i + 3 for i, v in enumerate(buf) if v]def solve(M, N, Cs):ps = primes2(M)dp = [0] * (M + 1)for c in Cs:if c > M:continuedp[M - c] = max(dp[M - c], 1)for m in range(M, c - 1, -1):if dp[m]:dp[m - c] = max(dp[m - c], dp[m] + 1)return max(dp) + sum(dp[p] for p in ps)print(solve(M, N, Cs))