Overview

Taking advantage of the small constraint \(N \leq 18\), we represent the set of chosen projects as a bitmask, enumerate all subsets to check whether they form an independent set (no conflicts), and compute the maximum profit within the budget.

Analysis

• At first glance, this problem resembles a knapsack problem in terms of “maximize profit within budget \(K\),” but it has an additional constraint that two conflicting projects cannot be selected simultaneously (an independent set constraint on a graph).
• Since \(K \leq 10^5\), even if we naively build a DP indexed by budget (\(O(NK)\)), handling the conflict constraint is difficult (we would need to track “which vertices have been selected” in the state), so this approach doesn’t work directly.
• On the other hand, since \(N \leq 18\), the total number of subsets is only \(2^N \leq 262144\).
  Therefore, the approach of “examining all subsets” is practical.
• However, if we check every edge for conflicts for each subset, it could become \(O(2^N \cdot M)\) depending on implementation, which is wasteful.
  Instead, we build up sets by adding one element at a time: “if the previous set was an independent set, we only need to check whether the newly added element conflicts with anything already in the set.”

Algorithm

1. Treat the conflict relationships as a graph, and for each project \(i\),
   store “the set of vertices conflicting with \(i\)” as a bitmask adj[i].
   • Example: if bit \(j\) of adj[i] is 1, then \(i\) and \(j\) cannot be selected simultaneously.
2. Represent each subset \(s\) (\(0\) to \(2^N - 1\)) as a bitmask.
   • Bit \(i\) of \(s\) is 1 ⇔ project \(i\) is selected.
3. For each subset, update the following values in a DP-like fashion:
   • cost[s]: total cost of set \(s\), i.e., \(\sum C_i\)
   • profit[s]: total profit of set \(s\), i.e., \(\sum P_i\)
   • ind[s]: True if set \(s\) contains no conflicts (is an independent set)
4. Transition construction:
   • Extract the lowest set bit of \(s\) (lsb), and let the corresponding element be \(i\)
     (i = lsb.bit_length() - 1).
   • Let prev = s ^ lsb. Then \(s\) is the set obtained by adding element \(i\) to prev.
   • The sums can always be computed:
     • cost[s] = cost[prev] + C[i]
     • profit[s] = profit[prev] + P[i]
   • The independent set check requires only the following:
     • ind[prev] is True (prev is an independent set)
     • AND prev and adj[i] do not intersect (= prev does not contain any vertex conflicting with \(i\))

          - In bitwise operations: `(prev & adj[i]) == 0`
       

     • If both conditions hold, then ind[s] = True
5. When ind[s] is True and cost[s] <= K, update the answer with profit[s].

In this way, the check for each set \(s\) reduces to “only checking conflicts with the single newly added element \(i\),” enabling efficient enumeration.

Complexity

• Time complexity: \(O(2^N)\)
  (For each subset, extracting the lowest bit, addition, and AND check are all constant-time operations)
• Space complexity: \(O(2^N)\)
  (Arrays for cost, profit, and ind)

Implementation Notes

• By storing conflict relationships as bitmasks adj[i] instead of adjacency lists, the conflict check reduces to a single operation: (prev & adj[i]) == 0.

• If we recalculate the total from scratch for each subset \(s\), it takes \(O(N)\) per subset. Instead, we update cost/profit incrementally from prev.

• Using lsb = s & -s (lowest set bit) and bit_length(), we can efficiently identify the added element \(i\).

  Source Code

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    if not it:
        return
    pos = 0
    N = it[pos]; M = it[pos+1]; K = it[pos+2]
    pos += 3

    C = [0] * N
    P = [0] * N
    for i in range(N):
        C[i] = it[pos]
        P[i] = it[pos+1]
        pos += 2

    adj = [0] * N
    for _ in range(M):
        u = it[pos] - 1
        v = it[pos+1] - 1
        pos += 2
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    size = 1 << N
    cost = [0] * size
    profit = [0] * size
    ind = [False] * size
    ind[0] = True

    ans = 0
    for s in range(1, size):
        lsb = s & -s
        i = lsb.bit_length() - 1
        prev = s ^ lsb

        cost_s = cost[prev] + C[i]
        profit_s = profit[prev] + P[i]
        cost[s] = cost_s
        profit[s] = profit_s

        if ind[prev] and (prev & adj[i]) == 0:
            ind[s] = True
            if cost_s <= K and profit_s > ans:
                ans = profit_s

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.