結果

問題 No.385 カップ麺生活
ユーザー roaris
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import defaultdict, deque
def era(n):
is_prime = [True]*(n+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n**0.5)+1):
if not is_prime[i]:
continue
for j in range(2*i, n+1, i):
is_prime[j] = False
return [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:
continue
for Ci in C:
if i-Ci>=0:
ins[i-Ci] += 1
outs[i].append(i-Ci)
q = deque([M])
dp = [-10**18]*(M+1)
dp[M] = 0
while q:
v = q.popleft()
for nv in outs[v]:
dp[nv] = max(dp[nv], dp[v]+1)
ins[nv] -= 1
if ins[nv]==0:
q.append(nv)
ans = 0
for pi in era(M-1):
if dp[pi]==-10**18:
continue
ans += dp[pi]
minC = min(C)
ans += max(dp[i] for i in range(minC) if dp[i]!=-10**18)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0