| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 559893 | PikaChu999 | Bank (IZhO14_bank) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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 banknotes 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];
banknotes = 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++) banknotes[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 banknotes
for(int b = 0; b < m; b++){ //last banknote used
if(a & (1 << b) == 1){
//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)] + banknotes[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)] + banknotes[b];
}
else if(left[a - (1 << b)] + banknotes[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();
}
}