제출 #810859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810859		Username_taken12	Bank (IZhO14_bank)	Java	19 / 100	756 ms	87604 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;
				if(dp[j][0]==N){
					pos=true;
					break;
				}
				for(int k=0; k<M; k++)
				{
					if((j&(1<<k))!=0)
						continue;
					if(dp[j][1]==mon[k])
						dp[j+(1<<k)]=new int[]{dp[j][0]+1, ppl[dp[j][0]+1]};
					if(dp[j][1]>mon[k])
						dp[j+(1<<k)]=new int[]{dp[j][0], dp[j][1]-mon[k]};
				}
			}
			if(pos)
				break;
		}
		if(pos)
			pw.println("YES");
		else
			pw.println("NO");
		pw.close();
	}
}

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