Overview

The problem of dividing all players into 2 teams can be rephrased as “finding a subset sum as close as possible to half of the total sum (a subset sum problem).”
Using a fast subset sum DP with a bit set (bitset), this can be solved efficiently within the constraints.

Analysis

First, let \(S_1\) be the total of Team 1, \(S_2\) be the total of Team 2, and \(T\) be the overall total sum. Then
\(S_1 + S_2 = T\).

We want to maximize \(\min(S_1, S_2)\), which is equivalent to “making the two sums as close as possible.”
Therefore, the answer is the maximum \(S_1\) that can be formed in the range \(S_1 \le \lfloor T/2 \rfloor\).

---

A brute-force approach of trying “assign each player to Team 1 or Team 2” requires \(2^N\) possibilities, which is infeasible for \(N \le 2\times10^4\).

Next, consider a typical 2D DP (dp[i][s]: whether sum \(s\) can be formed using the first \(i\) players).
The time complexity is \(O(NT)\). Here \(T=\sum A_i \le 2\times10^5\), so in theory it is large and tends to be slow in Python.

---

This is where bitset DP comes in.
If we maintain the “set of achievable sums” as a bit string, then << a corresponds to “adding \(a\) to every sum.”

• If bit \(i\) of dp is 1, then sum \(i\) is achievable
• Initially, only sum 0 is achievable, so dp = 1
• For each a, perform dp |= dp << a

This allows us to process one player’s update all at once using Python’s big integer arithmetic, executing it efficiently.

Finally, iterate from \(\lfloor T/2 \rfloor\) down to 0, and the first achievable sum \(s\) found is the answer (the maximum of \(\min(S_1,S_2)\)).

Algorithm

1. Read the input and compute the total sum \(T=\sum A_i\).
2. Initialize dp = 1 (sum 0 is achievable).
3. For each player’s strength a,
   perform dp |= (dp << a).
4. Set half = T // 2, and check s = half, half-1, ..., 0 in order.
5. Output the first s such that (dp >> s) & 1 == 1.

This s is the maximum value of \(\min(S_1, S_2)\).

Complexity

• Time complexity: \(O\!\left(N \cdot \frac{T}{w}\right)\) equivalent (\(w\) is the word size; speedup via bitset shift and OR operations)
• Space complexity: \(O(T)\) (bit string representing the set of reachable sums)

※ In practice, since the bitset is represented using Python’s arbitrary-precision integers, the constant factor is small and practical.

Implementation Notes

• dp = 1 means “only the 0th bit is set.”

• dp |= dp << a is the union of “not using a” and “using a.”

• At the end, by always searching downward from T//2, we can obtain the maximum value satisfying the condition.

• In this problem, the answer itself is \(\min(S_1,S_2)\), so the found s can be output directly.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]

    total = sum(A)
    # bit i of dp is 1 <=> sum i is achievable
    dp = 1
    for a in A:
        dp |= (dp << a)

    half = total // 2
    for s in range(half, -1, -1):
        if (dp >> s) & 1:
            print(s)
            return

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.