# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
800772 |
2023-08-01T20:19:56 Z |
Oz121 |
Bank (IZhO14_bank) |
Java 11 |
|
50 ms |
8396 KB |
import java.io.*;
import java.util.*;
public class bank {
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
int num = Integer.parseInt(l1.nextToken()); int m = Integer.parseInt(l1.nextToken());
int[] a = new int[num];
StringTokenizer st1 = new StringTokenizer(scan.readLine());
for (int i = 0;i<num;i++) {
a[i] = Integer.parseInt(st1.nextToken());
}
int[] b = new int[m];
StringTokenizer st2 = new StringTokenizer(scan.readLine());
for (int i = 0;i<m;i++) {
b[i] = Integer.parseInt(st2.nextToken());
}
Pair[] dp = new Pair[1<<num]; //Stores first i people we can satisfy and the leftover
dp[0] = new Pair(-1,0);
for (int i = 1;i<1<<num;i++) {
for (int j = 0;j<num;j++) {
if ((i&(1<<j))==0)
continue;
Pair prev = dp[i&(~(1<<j))];
if (prev.first==-1)
continue;
if (prev.left+b[j]==a[prev.first+1]) {
dp[i].first = prev.first+1; dp[i].left = 0;
break;
} else {
if (prev.first<dp[i].first)
continue;
dp[i].first = prev.first;
dp[i].left = prev.left+b[j];
}
}
}
boolean ans = false;
for (int i = 0;i<1<<num;i++) {
if (dp[i].first==num-1) {
ans = true;
}
}
if (ans)
System.out.println("YES");
else
System.out.println("NO");
}
public static class Pair {
int first; int left;
public Pair (int first, int left) {
this.first = first; this.left = left;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
50 ms |
8300 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
48 ms |
8396 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
49 ms |
8248 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
50 ms |
8300 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |