Submission #768349

#TimeUsernameProblemLanguageResultExecution timeMemory
768349iamjiamingliuBank (IZhO14_bank)Pypy 3
100 / 100
362 ms37200 KiB
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")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...