제출 #768339

#제출 시각아이디문제언어결과실행 시간메모리
768339iamjiamingliu은행 (IZhO14_bank)Pypy 3
71 / 100
1077 ms41900 KiB
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')
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...