Apple Division

n = int(input())
p = list(map(int, input().split()))

tot = sum(p)
half = tot // 2 + 1

dp = [False for _ in range(half)]
dups = [False for _ in range(half)]

dp[0] = True

for i in range(n):
    for j in range(half - p[i]):
        if dp[j]:
            dups[j + p[i]] = True

        for j in range(half):
            if dups[j]:
                dp[j] = True
            dups[j] = False

for i in range(half - 1, -1, -1):
    if dp[i]:
        print(tot-2*i)
        break

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: TIME LIMIT EXCEEDED

Test 18

Verdict: ACCEPTED