Submission #1088487

#TimeUsernameProblemLanguageResultExecution timeMemory
1088487vjudge1은행 (IZhO14_bank)Cpython 3
19 / 100
15 ms3420 KiB
n, m = map(int, input().split())

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

from collections import Counter
notas_count = Counter(notas)

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

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...