結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2020-03-06 13:49:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 63,616 KB |
最終ジャッジ日時 | 2024-10-04 23:02:22 |
合計ジャッジ時間 | 2,776 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#!/usr/bin/env python3# %%import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlines# %%M, N, *C = map(int, read().split())# %%U = 10 ** 4 + 10is_prime = [0] * Uis_prime[2] = 1for i in range(3, U, 2):is_prime[i] = 1for p in range(3, U, 2):if p * p > U:breakfor i in range(p * p, U, p + p):is_prime[i] = 0primes = [i for i, x in enumerate(is_prime) if x]# %%INF = 10 ** 9dp = [-INF] * (M + 1)dp[M] = 0for x in C:for n in range(M, x - 1, -1):y = dp[n] + 1if dp[n - x] < y:dp[n - x] = y# %%x = sum(max(0, dp[p]) for p in primes if p <= M)x += max(dp)print(x)