Overview

Since \(N \le 18\), we enumerate all possible subsets of employees using bitmasks, efficiently compute “sum of abilities − compatibility penalties” using subset DP, and find the maximum value among subsets of exactly \(K\) people.

Key Observations

When choosing a set of employees \(S\), the total power is:

• Sum of abilities: \(\sum_{i \in S} A_i\)
• Penalty: subtract \(B\) for each incompatible pair \((u,v)\) contained in \(S\)

A naive approach for each subset \(S\) would be: 1. Compute \(\sum A_i\) 2. Check all pairs to accumulate penalties (or check all \(M\) incompatible pairs)

However, there are \(2^N\) total subsets, and if we naively count penalties for each subset (e.g., taking \(O(M)\) per subset): - This becomes \(2^N \cdot M\), which tends to be too slow in Python even for \(N=18\).

The key insight is:

• If we build subsets by adding one element at a time via DP, we only need to subtract the penalties between the newly added employee and those already in the set.
• If we can quickly retrieve “the total penalty between employee \(i\) and all members of set \(S\)”, i.e., \(\sum_{j \in S} w[i][j]\), then each transition takes \(O(1)\).

Algorithm

1. Represent sets with bitmasks

We use a bit string mask of length \(N\), where bit \(i\) being 1 means employee \(i\) is selected (0-indexed).

2. Precomputation: penSum[i][mask]

We compute penSum[i][mask] = \sum_{j \in mask} w[i][j] for all \(i\) and mask.

This can be computed using subset DP. Let lsb be the lowest set bit of mask, and \(j\) be its position. Then:

• penSum[i][mask] = penSum[i][mask ^ lsb] + w[i][j]

This allows us to build all of penSum in \(O(N \cdot 2^N)\) total.

3. Subset DP: score[mask]

Let score[mask] be the total power when selecting the set mask.

When the lowest set bit of mask represents employee \(i\), prev = mask ^ lsb is the set excluding employee \(i\).

The change from prev to mask is:

• Ability: \(+A_i\)
• Newly incurred penalties: \(-\sum_{j \in prev} w[i][j]\)

Therefore:

[ score[mask] = score[prev] + A_i - penSum[i][prev] ]

With this formula, the penalty for an incompatible pair \((u,v)\) is subtracted exactly once — when the later-added member joins — so there is no double-counting or omission.

4. Answer

Among all mask values, we look only at those where bit_count() (the set size) equals \(K\), and take the maximum of score[mask].

Complexity

• Time complexity: \(O(N \cdot 2^N)\)
  (Building penSum takes \(O(N \cdot 2^N)\); the score DP takes \(O(2^N)\))
• Space complexity: \(O(N \cdot 2^N)\)
  (penSum is dominant; score is \(O(2^N)\))

Implementation Notes

• Using the lowest set bit (LSB)
  With lsb = mask & -mask and i = lsb.bit_length() - 1, we can decompose the transition into adding one element at a time.

• The precomputation to speed up penalty accumulation is crucial
  Since penSum[i][prev] can be retrieved in \(O(1)\), the transitions for score become fast.

• Speed optimization with arrays in Python
  The code uses array('q') (64-bit integers), which is more advantageous than lists in terms of memory and speed (the answer involves additions and subtractions on the order of \(10^9\), so 64-bit integers are safe).

  Source Code

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    K = next(it)

    A = [next(it) for _ in range(N)]

    w = [[0] * N for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        b = next(it)
        w[u][v] = b
        w[v][u] = b

    size = 1 << N

    penSum = []
    for i in range(N):
        arr = array('q', [0]) * size
        for mask in range(1, size):
            lsb = mask & -mask
            j = lsb.bit_length() - 1
            arr[mask] = arr[mask ^ lsb] + w[i][j]
        penSum.append(arr)

    score = array('q', [0]) * size
    for mask in range(1, size):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        prev = mask ^ lsb
        score[mask] = score[prev] + A[i] - penSum[i][prev]

    ans = -10**30
    for mask in range(size):
        if mask.bit_count() == K:
            v = score[mask]
            if v > ans:
                ans = v

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.