Submission #58459037

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solve(N, K):
    total_sum = sum(K)
    possible_sums = {0}
    
    for k in K:
        new_sums = set()
        for s in possible_sums:
            new_sums.add(s + k)
        possible_sums.update(new_sums)
    half_sum = total_sum // 2
    best_s = max(s for s in possible_sums if s <= half_sum)
    return max(best_s, total_sum - best_s)
N = int(input())
K = list(map(int, input().split()))
print(solve(N, K))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def solve(N, K):
    total_sum = sum(K)
    possible_sums = {0}
    
    for k in K:
        new_sums = set()
        for s in possible_sums:
            new_sums.add(s + k)
        possible_sums.update(new_sums)

    half_sum = total_sum // 2
    best_s = max(s for s in possible_sums if s <= half_sum)

    return max(best_s, total_sum - best_s)

N = int(input())
K = list(map(int, input().split()))

print(solve(N, K))

Submission Info

Judge Result