Overview

In a team formation problem where \(K\) people are selected from \(N\) employees, we want to maximize the “team’s overall strength,” which is the sum of each employee’s ability values minus penalties from incompatible pairs that end up on the same team.

Analysis

This problem is a combinatorial optimization problem where the team’s overall strength changes depending on which employees are selected. Thinking naively, we could try all combinations of choosing \(K\) people from \(N\), which amounts to \({}_N \mathrm{C}_K\) combinations. Given the constraint \(N \leq 18\), the maximum is around \({}_{18} \mathrm{C}_9 = 48620\), making exhaustive search feasible within practical computation time.

On the other hand, for each combination, we need to calculate the penalty from “incompatible pairs” included in the team. This can be computed efficiently by managing pair information in advance. Also, storing pairs \((u, v)\) in the order \(u < v\) makes them easier to handle.

Furthermore, penalties only occur “when both members of a pair are included in the team,” so we just need to check each pair for every team candidate.

In this way, the problem can be solved by trying all combinations while efficiently computing the score for each combination.

Algorithm

1. Read in the ability values \(A_i\) of employees and the incompatible pair information \((U_j, V_j, B_j)\).
2. Store the incompatible pairs in a dictionary bad with \((u, v)\) as the key and penalty \(b\) as the value (adjusted so that \(u < v\)).
3. Use itertools.combinations to generate all combinations of choosing \(K\) people from \(N\).
4. For each combination (team candidate):
   • First, calculate the sum of the team members’ ability values.
   • Then, if there are any incompatible pairs included in the team, subtract their penalties.
5. Record and output the maximum overall strength among all team candidates.

Complexity

• Time complexity: \(O\left(\binom{N}{K} \cdot M\right)\)
  • The number of combinations is at most \({}_{18}\mathrm{C}_9 \approx 4.8 \times 10^4\)
  • For each combination, we need to check up to \(M\) pairs.
• Space complexity: \(O(M + N)\)
  • The space needed to store the ability value list and pair information.

Implementation Notes

• Employee numbers are 1-indexed in the input, but converting to 0-indexed for internal processing makes them easier to handle.

• By always storing pairs \((u, v)\) in the order \(u < v\), dictionary lookups become straightforward.

• A set is used to quickly determine whether a specific employee is included in the team members (a list requires \(O(K)\), while a set averages \(O(1)\)).

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    A = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 相性の悪いペアを格納する辞書: (u, v) -> cost
    bad = {}
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        b = int(data[idx]); idx += 1
        if u > v:
            u, v = v, u
        bad[(u, v)] = b

    # 全てのK人組み合わせを試す
    from itertools import combinations
    max_power = -float('inf')
    
    for team in combinations(range(N), K):
        power = sum(A[i] for i in team)
        # チーム内の相性ペアをチェック
        team_set = set(team)
        for (u, v), cost in bad.items():
            if u in team_set and v in team_set:
                power -= cost
        if power > max_power:
            max_power = power
            
    print(max_power)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.