結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-02 14:07:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 714 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 68,284 KB |
最終ジャッジ日時 | 2024-10-04 22:37:25 |
合計ジャッジ時間 | 3,062 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
m = int(input())n = int(input())c = list(map(int,input().split()))c.sort(reverse=True)prime = []table = [True] * (m + 1)table[0] = table[1] = Falsefor i in range(2, m + 1):if not table[i]:continuek = i + iwhile k < m + 1:table[k] = Falsek += iprime.append(i)divp = [False] * 10001divpnum = []for i in range(len(prime)):divp[m - prime[i]] = Truedivpnum.append(m - prime[i])cost = [-1] * 20001cost[0] = 0for i in range(20001):for C in c:if cost[i] >= 0 and i + C <= m:cost[i + C] = max(cost[i] + 1, cost[i + C])ans = 0for i in divpnum:if cost[i] >= 0:ans += cost[i]ans += m // c[-1]print(ans)