結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-01 22:32:24 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 1,139 bytes |
コンパイル時間 | 1,803 ms |
コンパイル使用メモリ | 77,764 KB |
実行使用メモリ | 54,612 KB |
最終ジャッジ日時 | 2024-10-04 22:24:21 |
合計ジャッジ時間 | 6,788 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
package no385;import java.util.Arrays;import java.util.Scanner;public class Main {public static int INF = 1 << 29;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();}int[] dp = new int[m+1];Arrays.fill(dp, -INF);dp[0] = 0;for(int i=0;i<n;i++) {for(int j=c[i];j<=m;j++) {dp[j] = Math.max(dp[j], dp[j-c[i]] + 1);}}// System.out.println(Arrays.toString(dp));long ans = 0;boolean[] isPrime = isPrimeArray(m);for(int i=0;i<m;i++) {if (isPrime[i] && dp[m-i] >= 0) {ans += dp[m-i];}}int max = 0;for(int i=0;i<=m;i++) {max = Math.max(max, dp[i]);}ans += max;System.out.println(ans);}public static boolean[] isPrimeArray(int max) {boolean[] isPrime = new boolean[max+1];Arrays.fill(isPrime, true);isPrime[0] = isPrime[1] = false;for(int i=2;i*i<=max;i++) {if (isPrime[i]) {int j = i * 2;while(j<=max) {isPrime[j] = false;j += i;}}}return isPrime;}}