input()
people = list(map(int, input().split()))
banknotes = list(map(int, input().split()))
leftover = [-1] * (1 << len(banknotes))
people_covered = [-1] * (1 << len(banknotes))
leftover[0] = 0
people_covered[0] = 0
for s in range(1, 1 << len(banknotes)):
for last in range(len(banknotes)):
if not (s & (1 << last)):
continue
prev = s ^ (1 << last)
if people_covered[prev] == -1:
continue
new_amt = leftover[prev] + banknotes[last]
curr_target = people[people_covered[prev]]
if new_amt != curr_target:
people_covered[s] = people_covered[prev]
leftover[s] = new_amt
elif new_amt == curr_target:
people_covered[s] = people_covered[prev] + 1
leftover[s] = 0
if people_covered[s] == len(people):
print("YES")
exit()
print("NO")
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
18220 KB |
Output is correct |
2 |
Correct |
30 ms |
18148 KB |
Output is correct |
3 |
Correct |
41 ms |
18960 KB |
Output is correct |
4 |
Correct |
37 ms |
19108 KB |
Output is correct |
5 |
Correct |
302 ms |
35928 KB |
Output is correct |
6 |
Correct |
46 ms |
19032 KB |
Output is correct |
7 |
Correct |
48 ms |
18996 KB |
Output is correct |
8 |
Correct |
48 ms |
35820 KB |
Output is correct |
9 |
Correct |
293 ms |
36008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
44 ms |
19044 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
43 ms |
19564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
18220 KB |
Output is correct |
2 |
Correct |
30 ms |
18148 KB |
Output is correct |
3 |
Correct |
41 ms |
18960 KB |
Output is correct |
4 |
Correct |
37 ms |
19108 KB |
Output is correct |
5 |
Correct |
302 ms |
35928 KB |
Output is correct |
6 |
Correct |
46 ms |
19032 KB |
Output is correct |
7 |
Correct |
48 ms |
18996 KB |
Output is correct |
8 |
Correct |
48 ms |
35820 KB |
Output is correct |
9 |
Correct |
293 ms |
36008 KB |
Output is correct |
10 |
Incorrect |
44 ms |
19044 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |