Submission #1088496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088496		vjudge1	Bank (IZhO14_bank)	Cpython 3	19 / 100	15 ms	3420 KiB

bank

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")

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