Submission #560670

#TimeUsernameProblemLanguageResultExecution timeMemory
560670PikaChu999Bank (IZhO14_bank)Java
0 / 100
71 ms9028 KiB
/* 1 5 8 4 2 5 1 3 */ import java.util.*; import java.io.*; public class bank{ public static int n; //# of people to pay off public static int m; //# of notes left public static int[] people; public static int[] notes; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer details = new StringTokenizer(br.readLine()); n = Integer.parseInt(details.nextToken()); m = Integer.parseInt(details.nextToken()); people = new int[n]; notes = new int[m]; StringTokenizer ppl = new StringTokenizer(br.readLine()); for(int a = 0; a < n; a++) people[a] = Integer.parseInt(ppl.nextToken()); StringTokenizer bnk = new StringTokenizer(br.readLine()); for(int a = 0; a < m; a++) notes[a] = Integer.parseInt(bnk.nextToken()); int[] dp = new int[(1 << m)]; //dp[i] = mask of the most people that you can pay off given a mask of i notes int[] left = new int[(1 << m)]; Arrays.fill(dp, -1); Arrays.fill(left, -1); dp[0] = 0; left[0] = 0; boolean works = false; for(int a = 1; a < (1 << m); a++){ //mask of usable notes for(int b = 0; b < m; b++){ //last banknote used if((a & (1 << b)) > 0){ //try using this as the last banknote if(dp[a - (1 << b)] == -1) continue; //not possible, bank notes do not match up if(left[a - (1 << b)] + notes[b] < people[dp[b]]){ //covering each person in succession, assume bitmask will go over all cases and find the best one dp[a] = dp[a - (1 << b)]; left[a] = left[a - (1 << b)] + notes[b]; } else if(left[a - (1 << b)] + notes[b] == people[dp[b]]){ //fits! dp[a] = dp[a - (1 << b)] + 1; left[a] = 0; } } } if(dp[a] == n){ works = true; break; } } if(works) System.out.println("YES"); else System.out.println("NO"); br.close(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...