Submission #1088479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088479		vjudge1	Bank (IZhO14_bank)	Cpython 3	19 / 100	13 ms	3316 KiB

bank

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

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

def subset_sum(nums, target):
    dp = {0: []}
    
    for num in nums:
        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 binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def remove_subset_values(nums, subset):
    for value in subset:
        index = binary_search(nums, value)
        if index != -1:
            nums.pop(index)

possivel = 1

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

if possivel == 1: print("YES")
elif possivel == 0: print("NO")

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