Submission #877392

#	Time	Username	Problem	Language	Result	Execution time	Memory
877392		AI_2512	Bootfall (IZhO17_bootfall)	Cpython 3	0 / 100	11 ms	2908 KiB

bootfall

def split_array_helper(nums, index, sum1, sum2, arr1, arr2, cache):
    size = len(nums)
    if index == size:
        return sum1 == sum2

    key = tuple(arr1), tuple(arr2)
    if key in cache:
        return cache[key]

    arr1.append(nums[index])
    if split_array_helper(nums, index + 1, sum1 + nums[index], sum2, arr1, arr2, cache):
        cache[key] = True
        return True
    arr1.pop()

    arr2.append(nums[index])
    if split_array_helper(nums, index + 1, sum1, sum2 + nums[index], arr1, arr2, cache):
        cache[key] = True
        return True
    arr2.pop()

    cache[key] = False
    return False

def split_array(nums, arr1, arr2, cache):
    sum1, sum2 = 0, 0
    return split_array_helper(nums, 0, sum1, sum2, arr1, arr2, cache)

n = int(input())
arr = list(map(int, input().split()))
arr2, arr3 = [], []
res = []
total_sum = sum(arr)
cache = {}  # Cache for split_array function results

for i in range(1, total_sum + 1):
    ruined = False
    size = len(arr)

    if size > n:
        arr.pop()

    arr.append(i)

    to_delete = set(arr)

    for k in range(n + 1):
        if arr[k] in to_delete:
            continue

        arr2.append(arr[k])

        if not split_array(arr, arr2, arr3, cache):
            ruined = True
            break

        arr2.pop()

    if not ruined:
        res.append(i)

print(len(res))

if res:
    print(" ".join(map(str, res)))

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35