結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2019-12-11 20:57:32 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,133 bytes |
コンパイル時間 | 129 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 75,008 KB |
最終ジャッジ日時 | 2024-10-04 23:02:06 |
合計ジャッジ時間 | 2,816 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 RE * 1 |
ソースコード
from collections import defaultdict, dequedef era(n):is_prime = [True]*(n+1)is_prime[0] = Falseis_prime[1] = Falsefor i in range(2, int(n**0.5)+1):if not is_prime[i]:continuefor j in range(2*i, n+1, i):is_prime[j] = Falsereturn [i for i in range(n+1) if is_prime[i]]M = int(input())N = int(input())C = list(map(int, input().split()))if M==1:if min(C)==1:print(1)else:print(0)exit()ins = [0]*(M+1)outs = defaultdict(list)for i in range(M, -1, -1):if i!=M and ins[i]==0:continuefor Ci in C:if i-Ci>=0:ins[i-Ci] += 1outs[i].append(i-Ci)q = deque([M])dp = [-10**18]*(M+1)dp[M] = 0while q:v = q.popleft()for nv in outs[v]:dp[nv] = max(dp[nv], dp[v]+1)ins[nv] -= 1if ins[nv]==0:q.append(nv)ans = 0for pi in era(M-1):if dp[pi]==-10**18:continueans += dp[pi]minC = min(C)ans += max(dp[i] for i in range(minC) if dp[i]!=-10**18)print(ans)