結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2017-06-18 15:44:47 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 1,124 bytes |
コンパイル時間 | 1,827 ms |
コンパイル使用メモリ | 78,952 KB |
実行使用メモリ | 54,240 KB |
最終ジャッジ日時 | 2024-10-04 22:56:34 |
合計ジャッジ時間 | 6,831 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int M = sc.nextInt();int N = sc.nextInt();int[] c = new int[N];for(int i = 0; i < N; i++) {c[i] = sc.nextInt();}ArrayList<Integer> P = new ArrayList<Integer>();for(int i = 2; i < M; i++) {boolean flg = true;for(int j = 2; j * j <= i; j++) {if(i % j == 0) {flg = false;break;}}if(flg) P.add(i);}Arrays.sort(c);// dp[i]はちょうどi円購入したときの最大購入数を表す(不可能な場合は0)int[] dp = new int[M];for(int i = 1; i < M; i++) {for(int k = 0; k < N; k++) {if(i >= c[k]) {if(i == c[k]) {dp[i] = Math.max(dp[i], 1);} else {if(dp[i - c[k]] > 0) dp[i] = Math.max(dp[i], 1 + dp[i - c[k]]);}}}}int ans = 0;for(int i = 0; i < P.size(); i++) {ans += dp[M - P.get(i)];}ans += (M / c[0]);System.out.println(ans);}}