//package ojuz;
import java.io.*;
import java.util.*;
public class bank {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] first = reader.readLine().split(" ");
int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]);
int[] salary = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] notes = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] dp = new int[1 << m];
Arrays.fill(dp, -1);
dp[0] = 0;
int[] pd = new int[1 << m];
for (int i = 1; i < (1 << m); i++) {
for (int j = i; j > 0; j -= j & -j) {
int k = j & -j;
int idx = Integer.numberOfTrailingZeros(k);
if (dp[i ^ k] == -1) continue;
int cmp = Integer.compare(pd[i ^ k] + notes[idx], salary[dp[i ^ k]]);
int newDp = dp[i ^ k], newPd = pd[i ^ k];
if (cmp == 0) {
// adding this note completes a persons salary
newDp++;
newPd = 0;
} else if (cmp < 0) {
// adding this note partially completes a persons salary
newPd += notes[idx];
}
// same prefix done, maximize part done
if (newDp == dp[i]) pd[i] = Math.max(pd[i], newPd);
// greater prefix done
else if (newDp > dp[i]) {
dp[i] = newDp;
pd[i] = newPd;
}
}
if (dp[i] == n) {
System.out.println("YES");
return;
}
}
System.out.println("NO");
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |