結果
問題 |
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] = False for i in range(2, m + 1): if not table[i]: continue k = i + i while k < m + 1: table[k] = False k += i prime.append(i) divp = [False] * 10001 divpnum = [] for i in range(len(prime)): divp[m - prime[i]] = True divpnum.append(m - prime[i]) cost = [-1] * 20001 cost[0] = 0 for 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 = 0 for i in divpnum: if cost[i] >= 0: ans += cost[i] ans += m // c[-1] print(ans)