結果
問題 |
No.385 カップ麺生活
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:49:45 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,360 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 67,492 KB |
最終ジャッジ日時 | 2025-03-20 20:49:48 |
合計ジャッジ時間 | 2,969 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 WA * 4 |
ソースコード
M = int(input())N = int(input())C = list(map(int, input().split()))# Sieve of Eratosthenes to find primes up to Mdef sieve(n):if n < 2:return [False] * (n + 1), []is_prime = [True] * (n + 1)is_prime[0], is_prime[1] = False, Falsefor i in range(2, int(n ** 0.5) + 1):if is_prime[i]:for j in range(i * i, n + 1, i):is_prime[j] = Falseprimes = [i for i, prime in enumerate(is_prime) if prime]return is_prime, primesis_prime, primes_list = sieve(M)# DP to compute the maximum number of cups for each sum up to Mmax_num = [-1] * (M + 1)max_num[0] = 0 # Base case: 0 money buys 0 cupsfor x in range(M + 1):if max_num[x] == -1:continuefor c in C:next_x = x + cif next_x > M:continueif max_num[next_x] < max_num[x] + 1:max_num[next_x] = max_num[x] + 1# Calculate the sum of valid k_p valuessum_k = 0for p in primes_list:required = M - pif required >= 0 and max_num[required] > 0:sum_k += max_num[required]# Calculate the maximum x for the last non-reset purchasemax_x = 0for x in range(M + 1):r = M - xif r < 0:continueif r == 0 or not is_prime[r]:if max_num[x] != -1 and max_num[x] > max_x:max_x = max_num[x]print(sum_k + max_x)