結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2021-02-05 05:47:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 554 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 62,976 KB |
最終ジャッジ日時 | 2024-10-04 23:07:03 |
合計ジャッジ時間 | 2,484 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
def Eratosthenes(N): #N以下の素数のリストを返すN+=1is_prime_list = [True]*Nm = int(N**0.5)+1for i in range(3,m,2):if is_prime_list[i]:is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)return [2] + [i for i in range(3,N,2) if is_prime_list[i]]m,n,*a = map(int,open(0).read().split())dp = [-10**9]*(m+1)dp[0] = 0for ai in a:for i in range(ai,m+1):dp[i] = max(dp[i],dp[i-ai] + 1)primes = Eratosthenes(m)ans = 0for i in primes:ans += max(0,dp[m-i])print(ans + max(dp))