結果

問題 No.385 カップ麺生活
ユーザー 37zigen37zigen
提出日時 2016-07-01 23:30:18
言語 Java21
(openjdk 21)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 3,737 bytes
コンパイル時間 2,449 ms
コンパイル使用メモリ 80,812 KB
実行使用メモリ 42,360 KB
最終ジャッジ日時 2024-04-15 07:28:25
合計ジャッジ時間 8,977 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 145 ms
41,520 KB
testcase_01 AC 145 ms
41,832 KB
testcase_02 AC 136 ms
41,540 KB
testcase_03 AC 147 ms
41,920 KB
testcase_04 AC 149 ms
41,964 KB
testcase_05 AC 149 ms
42,084 KB
testcase_06 AC 152 ms
41,996 KB
testcase_07 AC 154 ms
42,120 KB
testcase_08 AC 150 ms
41,804 KB
testcase_09 AC 134 ms
42,216 KB
testcase_10 AC 173 ms
42,068 KB
testcase_11 AC 132 ms
41,808 KB
testcase_12 AC 153 ms
41,904 KB
testcase_13 AC 156 ms
42,012 KB
testcase_14 AC 163 ms
42,032 KB
testcase_15 AC 162 ms
41,992 KB
testcase_16 AC 147 ms
41,776 KB
testcase_17 AC 169 ms
42,000 KB
testcase_18 AC 152 ms
42,188 KB
testcase_19 AC 148 ms
41,960 KB
testcase_20 AC 159 ms
41,728 KB
testcase_21 AC 160 ms
41,984 KB
testcase_22 AC 157 ms
42,068 KB
testcase_23 AC 168 ms
41,976 KB
testcase_24 AC 160 ms
42,360 KB
testcase_25 AC 146 ms
41,996 KB
testcase_26 AC 164 ms
42,176 KB
testcase_27 AC 165 ms
42,048 KB
testcase_28 AC 170 ms
41,604 KB
testcase_29 AC 152 ms
41,484 KB
testcase_30 AC 162 ms
41,648 KB
testcase_31 AC 149 ms
42,160 KB
testcase_32 AC 150 ms
42,036 KB
testcase_33 AC 165 ms
42,044 KB
testcase_34 AC 157 ms
41,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class  Main{
	public static void main(String[] args){
		new Main().solver();
	}
	void solver(){
		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();
		}

		// size is 1229
		ArrayList<Integer> primeList=primeList(10010);

		Arrays.sort(C);

		int[] possible_num=new int[10010];



		for(int j=M;j>=0;j--){
			for(int i=0;i<N;i++){
				if(j+C[i]<=M){
					if(possible_num[j+C[i]]>0||j+C[i]==M)
						possible_num[j]=Math.max(possible_num[j+C[i]]+1,possible_num[j]);
				}
			}
		}
		long ans=0;
		long max=0;
		for(int i=1;i<M;i++){
			if(primeList.contains(i)){
				ans+=possible_num[i];
//				System.out.println(i+" "+possible_num[i]);
			}
		}
		for(int i=0;i<M;i++){
			max=Math.max(max, possible_num[i]);
		}
		ans+=max;
		System.out.println(ans);

	}
	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]){
				for(int j=2;j*i<=max;j++){
					isPrime[j*i]=false;
				}
			}
		}
		return isPrime;
	}
	/*
	 * max以下の素数のリストを返す
	 */
	ArrayList<Integer> primeList(int max){
		boolean[] isPrime=isPrimeArray(max);
		ArrayList<Integer> primeList=new ArrayList<Integer>();
		for(int i=2;i<=max;i++){
			if(isPrime[i]){
				primeList.add(i);
			}
		}
		return primeList;
	}
	/*
	 * numをprimeListの素数をもとに素因数分解し、因数を
	 * ArrayList<Factor>の形で返す。1は含まれない。
	 * primeListにはnumの平方根以下の素数が含まれていなければならない。
	 *
	 */
	ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList,long num){
		ArrayList<Factor> ret=new ArrayList<Factor>();
		for(int p:primeList){
			int exp=0;
			while(num%p==0){
				num/=p;
				exp++;
			}
			if(exp>0)ret.add(new Factor(p,exp));
		}
		if(num>1)ret.add(new Factor(num,1));
		return ret;
	}
	class Factor{
		long base,exp;
		Factor(long base,long exp){
			this.base=base;
			this.exp=exp;
		}
	}
	/*
	 * 戻り値：約数の和
	 * verified:yukicoder No.278
	 */
	long sum_d(ArrayList<Factor> fs){
		long sum=1;
		for(Factor f:fs){
			sum*=Long.parseLong((BigInteger.ONE.subtract(pow_big(f.base,f.exp+1))).divide(BigInteger.ONE.subtract(BigInteger.valueOf(f.base))).toString());
		}
		return sum;
	}
	BigInteger pow_big(long a,long n){
		BigInteger A=new BigInteger(String.valueOf(a));
		BigInteger ans=BigInteger.ONE;
		while(n>=1){
			if(n%2==0){
				A=A.multiply(A);
				n/=2;
			}else if(n%2==1){
				ans=ans.multiply(A);
				n--;
			}
		}
		return ans;
	}

	/*Verified:yukicoder377
	 * Eulerのφ関数(Euler's totient function) 1からnまでの自然数のうちnと互いに素なものの個数を数える。
	 * φ(mn)=φ(m)φ(n) (gcd(m,n)=1) なぜならば、chinese reminder theoremより、 a mod mnと
	 * (a mod n)と(b mod m)は全単射。 φ(p^k)=p^k-p^(k-1)=p^k(1-1/p)
	 * よってφ(p^k*q^k)=n(1-1/p)(1-1/q)という風にできる。
	 */

	long totient_function(ArrayList<Factor> f, long n) {
		long ret = n;
		for (int i = 0; i < f.size(); i++) {
			ret = ret - ret / f.get(i).base;
		}
		return ret;
	}
	// nの約数を列挙。1とnを含む。
	ArrayList<Long> enum_div(ArrayList<Factor> f) {
		ArrayList<Long> ret = new ArrayList<Long>();
		ret.add(1L);
		for (int i = 0; i < f.size(); i++) {
			long a = 1;
			int n = ret.size();
			for (int j = 0; j < f.get(i).exp; j++) {
				a *= f.get(i).base;
				for (int k = 0; k < n; k++) {
					ret.add(ret.get(k) * a);
				}
			}
		}
		return ret;
	}
}
0