Overview

Brute-forcing all “select/don’t select” choices for each security company would result in \(2^N\) combinations, which is far too large.
Instead, we represent the “set of facilities covered so far” as a bitmask and update the minimum cost while examining companies one by one — this is a bit DP (subset DP) approach.

Key Observations

The crucial point is the constraints: \(N \le 50, M \le 18\).
\(N\) is moderately large, but \(M\) is small.

• Directly enumerating all ways to choose companies gives \(2^N\) (up to \(2^{50}\)), which is infeasible.
• On the other hand, the number of facility states is \(2^M\) (up to \(2^{18}=262144\)), which is practical.

In other words, instead of tracking “which companies were selected,”
it is effective to use “which facilities have been covered so far” as the state.

---

Convert the set of facilities that each company \(i\) can cover into a bitmask mask[i].
For example, if \(M=5\) and a company can guard facilities 1 and 3, this is represented as 00101 (the bit-position mapping depends on the implementation).

Define the DP as follows:

• dp[s] = “the minimum cost to cover the facility set s”

The initial state has nothing covered, so dp[0]=0.
For each company we examine:

• Don’t select: the state remains unchanged
• Select: transition to ns = s | mask[i], adding cost + C[i]

This is a 0/1 knapsack-style update. In the code, we use ndp = dp[:] to preserve the “don’t select” case and then apply the “select” case.

Finally, the state covering all facilities is ((1<<M)-1), so the minimum value at that state is the answer. If it is unreachable, output -1.

Algorithm

1. Read the input and convert each company \(i\)’s list of guardable facilities \(E_{i,*}\) into a bitmask masks[i].
2. Set size = 1<<M, prepare dp of length size with dp[0]=0 and all others as INF.
3. For each company \(i=0..N-1\), do the following:
   • ndp = dp[:]
   • For every state s, if dp[s] is valid:
     • ns = s | masks[i]
     • ndp[ns] = min(ndp[ns], dp[s] + C[i])
   • dp = ndp
4. Let full = (1<<M)-1 and check dp[full]. If it equals INF, output -1; otherwise, output that value.

Complexity

• Time complexity: \(O(N \cdot 2^M)\)
• Space complexity: \(O(2^M)\)

(For N=50, M=18, this is approximately \(50 \times 262144\), which is well within time limits.)

Implementation Notes

• Facility sets are handled efficiently using bit operations (|, <<).

• Set INF to a sufficiently large value (e.g., 10**30) to prevent overflow or comparison errors.

• Since each company can only be used once, use ndp during updates to prevent “reusing the same company.”

• Don’t forget to output -1 if the final state full = (1<<M)-1 cannot be reached.

  Source Code

import sys

def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    C = list(map(int, input().split()))

    masks = []
    for _ in range(N):
        e = list(map(int, input().split()))
        mask = 0
        for j, v in enumerate(e):
            if v == 1:
                mask |= (1 << j)
        masks.append(mask)

    INF = 10**30
    size = 1 << M
    dp = [INF] * size
    dp[0] = 0

    for i in range(N):
        ndp = dp[:]  # 選ばない場合を保持
        cm = masks[i]
        cost = C[i]
        for s in range(size):
            if dp[s] == INF:
                continue
            ns = s | cm
            v = dp[s] + cost
            if v < ndp[ns]:
                ndp[ns] = v
        dp = ndp

    ans = dp[size - 1]
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.