Submission #810884

#	Time	Username	Problem	Language	Result	Execution time	Memory
810884		Username_taken12	Bank (IZhO14_bank)	Java	100 / 100	684 ms	88788 KiB

bank

// Source: https://usaco.guide/general/io

import java.io.*;
import java.util.*;
import java.lang.Integer;

public class bank {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] ppl = new int[N+1];
		ppl[N]=0;
		int[] mon = new int[M];

		st= new StringTokenizer(r.readLine());
		for(int i = 0; i<N; i++)
			ppl[i]=Integer.parseInt(st.nextToken());
		st= new StringTokenizer(r.readLine());
		for(int j=0; j<M; j++)
			mon[j]=Integer.parseInt(st.nextToken());

		int[][] dp = new int[(1<<M)][2]; //ppl remaining
		for(int i=0; i<(1<<M); i++)
			dp[i]=new int[]{-1, Integer.MAX_VALUE};
		dp[0]=new int[]{0, ppl[0]};

		boolean pos=false;
		for(int i=0; i<M+1; i++){
			for(int j = 0; j<(1<<M); j++)
			{
				if(Integer.bitCount(j)!=i)
					continue;
				//System.out.println(Integer.toBinaryString(j));
				//System.out.println(Arrays.toString(dp[j]));
				if(dp[j][0]==N){
					pos=true;
					break;
				}
				if(dp[j][0]==-1)
					continue;
				for(int k=0; k<M; k++)
				{	
					//System.out.print(k);
					if((j&(1<<k))!=0){
						//System.out.println(" continue!");
						continue;
					}
					
					//System.out.println();
					if(dp[j][1]==mon[k]){
						
						dp[j+(1<<k)]=new int[]{dp[j][0]+1, ppl[dp[j][0]+1]};
						//if(dp[j][0]+1==N)
						//	System.out.println(j+(1<<k)+" "+Arrays.toString(dp[j+(1<<k)]));
					}
					if(dp[j][1]>mon[k])
						dp[j+(1<<k)]=new int[]{dp[j][0], dp[j][1]-mon[k]};
				}

			}
			//System.out.println();
			if(pos)
				break;
		}
		//for(int i=0; i)

		if(pos)
			pw.println("YES");
		else
			pw.println("NO");
		pw.close();
	}
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29