제출 #1088496

#제출 시각아이디문제언어결과실행 시간메모리
1088496vjudge1은행 (IZhO14_bank)Cpython 3
19 / 100
15 ms3420 KiB
from collections import Counter

def subset_sum(nums_count, target):
    dp = {0: []}
    
    for num, count in nums_count.items():
        for _ in range(count):
            new_sums = {}
            for partial_sum, subset in dp.items():
                new_sum = partial_sum + num
                if new_sum == target:
                    return subset + [num]
                if new_sum < target:
                    new_sums[new_sum] = subset + [num]
            dp.update(new_sums)
    
    return None

def remove_subset_values(nums_count, subset):
    for value in subset:
        if nums_count[value] > 0:
            nums_count[value] -= 1


n, m = map(int, input().split())

valores = list(map(int, input().split()))
notas = list(map(int, input().split()))

notas_count = Counter(notas)

possivel = 1

for v in valores:
    solution = subset_sum(notas_count, v)
    if solution is None:
        possivel = 0
        break
    else:
        remove_subset_values(notas_count, solution)

if possivel == 1:
    print("YES")
else:
    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...