Submission #429408

#	Time	Username	Problem	Language	Result	Execution time	Memory
429408		SansPapyrus683	Bank (IZhO14_bank)	Cpython 3	0 / 100	75 ms	3148 KiB

bank

from sys import exit

people_num, note_num = [int(i) for i in input().split()]
people = [int(i) for i in input().split()]
banknotes = [int(i) for i in input().split()]

leftover = [-1 for _ in range(1 << note_num)]
people_covered = [-1 for _ in range(1 << note_num)]
leftover[0] = 0
people_covered[0] = 0
for s in range(1, 1 << note_num):
    for last in range(people_num):
        if (s & (1 << last)) == 0:
            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] == people_num:
        print("YES")
        exit()
print("NO")

• Subtask 1: 0 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29