Overview

From \(N\) employees, select \(K\) to form a team, and maximize the “team’s total power” which is calculated as the sum of ability values minus the reduction from incompatible pairs.

Analysis

Key Observations

• Notice that the constraint \(N \leq 18\) is very small
• The total number of ways to choose \(K\) people from \(N\) people is \(\binom{N}{K}\)
• When \(N = 18\), there are at most about \(\binom{18}{9} = 48620\) combinations

Why a Naive Approach is Sufficient

Normally, an approach that enumerates all combinations has exponential time complexity and would result in TLE for large \(N\). However, in this problem: - \(N \leq 18\) is small - The number of combinations is at most about 50,000 - The processing for each combination is about \(O(K + M)\)

Therefore, a brute force search is sufficient.

Concrete Example

For example, if \(N = 4\), \(K = 2\), employee ability values are \([10, 20, 30, 5]\), and there is an incompatible pair \((1, 3)\) with reduction \(15\):

Team	Ability Sum	Reduction	Total Power
{1, 2}	10+20=30	0	30
{1, 3}	10+30=40	15	25
{1, 4}	10+5=15	0	15
{2, 3}	20+30=50	0	50 ← Maximum
{2, 4}	20+5=25	0	25
{3, 4}	30+5=35	0	35

Algorithm

1. Enumerate all combinations: Use itertools.combinations to generate all combinations of choosing \(K\) people from \(N\) people
2. For each combination:
   • Sum the ability values of the selected employees
   • For each incompatible pair \((U_j, V_j)\), if both are in the team, subtract \(B_j\)
3. Update the maximum: If the calculated total power is greater than the current maximum, update it
4. Output the result: Output the final maximum value

Complexity

• Time Complexity: \(O(\binom{N}{K} \times (K + M))\)

  • Enumerate \(\binom{N}{K}\) combinations
  • For each combination, \(O(K)\) to sum ability values and \(O(M)\) to check pairs
  • When \(N = 18\), at most about \(48620 \times (18 + 153) \approx 8.3 \times 10^6\) operations

• Space Complexity: \(O(N + M)\)

  • \(O(N)\) for the ability value array \(A\)
  • \(O(M)\) for the list of incompatible pairs
  • \(O(K)\) for managing the team as a set

Implementation Notes

1. Converting to 0-indexed: Since the input employee numbers start from 1, subtract -1 to convert to 0-indexed for array access

2. Using sets: By storing selected members in a set, checking whether a specific employee is in the team can be done in \(O(1)\)

3. Setting initial value: Setting the initial maximum value to -float('inf') ensures correct handling even when reductions are large enough to make the result negative

Source Code

from itertools import combinations

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Store information about incompatible pairs
    bad_pairs = []
    for _ in range(M):
        U, V, B = map(int, input().split())
        bad_pairs.append((U - 1, V - 1, B))  # Convert to 0-indexed
    
    max_power = -float('inf')
    
    # Enumerate all combinations of choosing K people from N people
    for team in combinations(range(N), K):
        team_set = set(team)
        
        # Sum of ability values of selected employees
        total = sum(A[i] for i in team)
        
        # Calculate reduction from incompatible pairs
        for U, V, B in bad_pairs:
            if U in team_set and V in team_set:
                total -= B
        
        max_power = max(max_power, total)
    
    print(max_power)

solve()

---

This editorial was generated by claude4.5opus.