oj.uz

Submission #877392

# Submission time Handle Problem Language Result Execution time Memory
877392 2023-11-23T08:08:22 Z AI_2512 Bootfall (IZhO17_bootfall) Python 3
0 / 100
 11 ms 2908 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -