結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2023-08-02 18:42:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 1,601 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 100,864 KB |
最終ジャッジ日時 | 2024-10-12 15:47:54 |
合計ジャッジ時間 | 7,293 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,mathinput = sys.stdin.readlineM = int(input())N = int(input())C = list(map(int,input().split()))class prime_factorize():def __init__(self,M=10**6):self.sieve = [-1]*(M+1)self.sieve[1] = 1self.p = [False]*(M+1)self.mu = [1]*(M+1)for i in range(2,M+1):if self.sieve[i] == -1:self.p[i] = Truei2 = i**2for j in range(i2,M+1,i2):self.mu[j] = 0for j in range(i,M+1,i):self.sieve[j] = iself.mu[j] *= -1def factors(self,x):tmp = []while self.sieve[x] != x:tmp.append(self.sieve[x])x //= self.sieve[x]tmp.append(self.sieve[x])return tmpdef is_prime(self,x):return self.p[x]def mobius(self,x):return self.mu[x]pf = prime_factorize()dp = [-1]*(M+1)dp[0]=0for i in range(N):c = C[i]if c>M:continueif dp[c]==-1:dp[c]=1for j in range(M+1-c):if dp[j]!=-1:dp[j+c]=max(dp[j+c],dp[j]+1)# for i in range(M+1):# if dp[i]!=-1:# print(i,dp[i])ans = sum(dp[i]*pf.is_prime(M-i)*(dp[i]!=-1) for i in range(M+1)) + max(dp[i] for i in range(M+1))print(ans)