Overview

This problem involves dividing players into 2 teams, but it is essentially a problem of “finding the maximum subset sum that does not exceed half of the total sum \(T=\sum A_i\).”
By treating it as a subset sum problem and using bitset DP, we can solve it efficiently.

Analysis

First, let \(S_1\) be the total strength of team 1 and \(S_2\) be the total strength of team 2. Then,

\(S_1 + S_2 = T\)

Therefore, once the sum of one team is determined, the other is automatically determined as well.

Here, assuming \(S_1 \leq S_2\), we have

\(\min(S_1, S_2)=S_1\)

In other words, to make the match as competitive as possible, we need to find:

• A subset sum as large as possible
• Without exceeding \(T/2\)

In other words, if we:

• Assign certain players to team 1
• Let their total strength be \(s\)

Then the answer is

\(\max \{ s \mid s \leq \lfloor T/2 \rfloor,\ s \text{ is achievable} \}\)

---

Why naive approaches don’t work

1. Brute force

Since each player is assigned to either team 1 or team 2, the number of cases is \(2^N\).
With \(N \leq 2 \times 10^4\), this is obviously infeasible.

2. Standard subset sum DP

A common DP approach uses:

• \(dp[s] = \text{whether sum } s \text{ is achievable}\)

The transition takes \(O(NT)\), where \(T=\sum A_i \leq 2 \times 10^5\).

Substituting the constraints, the maximum is approximately

\(2 \times 10^4 \times 2 \times 10^5 = 4 \times 10^9\)

which is too slow for Python.

---

How to speed it up

Here, we store dp[s] as a bit string instead of an array.

• If bit \(s\) is 1, “sum \(s\) is achievable”
• If bit \(s\) is 0, “not achievable”

In the initial state, only sum \(0\) (selecting nothing) is achievable, so

• dp = 1

In binary, this is ...0001, meaning only bit 0 is set.

When a player’s strength is \(a\):

• The sums that were already achievable
• Those sums plus \(a\)

both become newly achievable.
This can be written using bit operations as:

dp |= dp << a

dp << a corresponds to “adding \(a\) to every currently achievable sum.”
By repeating this for all players, we can determine all achievable subset sums.

---

Concrete example

Consider \(A = [3, 5, 6]\).

The total is \(T=14\), and half is \(7\).

• Initial: dp = 1
  Achievable sums: \(\{0\}\)

• Using \(3\): dp |= dp << 3
  Achievable sums: \(\{0,3\}\)

• Using \(5\):
  Achievable sums: \(\{0,3,5,8\}\)

• Using \(6\):
  Achievable sums: \(\{0,3,5,6,8,9,11,14\}\)

Among these, the maximum that is \(7\) or less is \(6\), so the answer is \(6\).
Indeed, the other team has \(14-6=8\), so \(\min(6,8)=6\) is maximized.

Algorithm

1. Read the input and compute the total \(T=\sum A_i\).
2. Set dp = 1.
   This represents “sum 0 is achievable.”
3. For each \(a \in A\),
   perform dp |= dp << a.
4. Compute \(half = \lfloor T/2 \rfloor\).
5. Extract only the bits from \(0\) to half in dp.
6. Output the highest set bit position as the answer.

In code:

mask = (1 << (half + 1)) - 1
ans = (dp & mask).bit_length() - 1

Here’s how it works:

• mask is an integer with only the lowest half+1 bits set to 1
• dp & mask keeps only the “achievable sums that are \(half\) or less”
• bit_length() - 1 gives the position of the highest set bit, i.e., the maximum achievable sum

Complexity

Let \(S=\sum A_i\).

• Time complexity: \(O\left(N \cdot \frac{S}{w}\right)\) equivalent
  
• Space complexity: \(O(S)\)

Here, \(w\) is the number of bits per word.
This is significantly faster than the \(O(NS)\) of the standard array DP, and is fast enough even in Python.

Implementation notes

• The key point is that dp represents a bit set using “a single integer.”

• dp |= dp << a directly corresponds to the subset sum DP transition.

• Since we only need the maximum value that is \(T/2\) or less at the end, we extract only the lower bits using mask.

• bit_length() returns “the position of the highest set bit + 1”, so the maximum sum is bit_length() - 1.

  Source Code

import sys

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

    total = sum(A)
    dp = 1  # dp[s] = reachable 여부를 비트 s로表現

    for a in A:
        dp |= dp << a

    half = total // 2
    mask = (1 << (half + 1)) - 1
    ans = (dp & mask).bit_length() - 1
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.