Submission #561492

#	Time	Username	Problem	Language	Result	Execution time	Memory
561492		PikaChu999	Bank (IZhO14_bank)	Java	100 / 100	304 ms	18560 KiB

bank

/*
1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11
*/
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[a - (1 << 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[a - (1 << b)]]){
            //fits!
            dp[a] = dp[a - (1 << b)] + 1; 
            left[a] = 0; 
          }
        }
      }
      if(dp[a] == n){
        //System.out.println(Integer.toBinaryString(a));
        works = true; 
        break; 
      }
    }

    if(works) System.out.println("YES");    
    else System.out.println("NO");
    br.close();
  }
}

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