Submission #768339

#	Time	Username	Problem	Language	Result	Execution time	Memory
768339		iamjiamingliu	Bank (IZhO14_bank)	Pypy 3	71 / 100	1077 ms	41900 KiB

bank

input()
salaries = list(map(int, input().split()))
notes = list(map(int, input().split()))

if len(salaries) > len(notes):
    print('NO')
    exit()

combo_to_form = {val: [] for val in salaries}
for subset in range(1 << len(notes)):
    subset_sum = sum(notes[j] for j in range(subset.bit_length()) if (1 << j) & subset)
    if subset_sum in salaries:
        combo_to_form[subset_sum].append(subset)

if not all(combo_to_form.values()):
    print('NO')
    exit()

prev_subsets = {(1 << len(notes)) - 1}
for val in salaries:
    new_subsets = set()
    for prev in prev_subsets:
        for needed in combo_to_form[val]:
            if (prev & needed) == needed:
                new_subsets.add(prev - needed)
    if not new_subsets:
        print('NO')
        exit()
    prev_subsets = new_subsets

print('YES')

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