結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2020-11-29 22:35:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 827 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 81,992 KB |
実行使用メモリ | 65,052 KB |
最終ジャッジ日時 | 2024-10-04 23:06:34 |
合計ジャッジ時間 | 3,062 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from itertools import chain, productdef prime_set(N):"""Nまでの素数のsetを返す"""if N < 4:return ({}, {}, {2}, {2, 3})[N]Nsq = int(N ** 0.5 + 0.5) + 1primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))for i in range(5, Nsq, 2):if i in primes:primes -= set(range(i * i, N + 1, i * 2))return primesM = int(input())N = int(input())C = list(map(int, input().split()))prime = prime_set(M+10)dp = [-1] * (M + 1)dp[0] = 0for c in C:for i in range(M):if dp[i] == -1:continueif i + c <= M:dp[i + c] = max(dp[i + c], dp[i] + 1)ans = 0for cost, buy in enumerate(dp):if buy == -1:continueif M - cost in prime:ans += buyans += M // min(C)print(ans)