結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-02 11:51:15 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 1,292 bytes |
コンパイル時間 | 71 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-10-04 22:35:24 |
合計ジャッジ時間 | 2,614 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#!/usr/bin/env python3# Based on http://pakapa104.hatenablog.com/entry/2016/07/02/014219import arrayINF = 10 ** 9def sieve_of_eratosthenes(end):is_prime = array.array("B", (True for i in range(end)))is_prime[0] = Falseis_prime[1] = Falsefor i in range(2, end):if is_prime[i]:for j in range(2 * i, end, i):is_prime[j] = Falsereturn is_primedef compute_max_cups(init_money, cups):# 個数制限のないナップザック問題をボトムアップの動的計画法で解く# dp[i] = (所持金がiになるまでに買えるカップ麺の数)dp = array.array("l", (-INF for _ in range(init_money + 1)))dp[init_money] = 0for cup in cups:for i in range(init_money - cup + 1)[::-1]:dp[i] = max(dp[i], dp[i + cup] + 1)# 素数表を得るis_prime = sieve_of_eratosthenes(init_money + 1)# 金欠チャンスの処理# その後は、買えるだけ買うreturn sum(dp[i] for i in range(1, init_money + 1)if dp[i] > 0 and is_prime[i]) + max(dp)def main():m = int(input())_ = int(input())cs = array.array("L", map(int, input().split()))print(compute_max_cups(m, cs))if __name__ == '__main__':main()