Overview

This is a problem of maximizing the total weight of selected vertices under the constraint that no two adjacent vertices on a graph are selected simultaneously (independent set), with the total not exceeding \(M\). Given the constraint \(N \leq 40\), we solve it by combining Meet in the Middle with SOS DP for max over subsets.

Analysis

Essence of the Problem

This problem can be reduced to the maximum weight independent set problem. We treat sections as graph vertices and corridors as edges, select vertices such that no two adjacent vertices are chosen simultaneously, and maximize \(\min(\text{total}, M)\) of the weights (\(P_i\)) of the selected vertices.

Naive Approach

One could enumerate all \(2^N\) subsets of vertices, check whether each is an independent set, and find the maximum weight. However, when \(N \leq 40\), this gives \(2^{40} \approx 10^{12}\) subsets, which is far too slow.

What if \(N \leq 20\)?

Since \(2^{20} \approx 10^6\), full enumeration is feasible. This gives us a hint, leading to the idea of splitting \(N\) in half and applying Meet in the Middle.

Challenge of Combining After Splitting in Half

When combining an independent set from the first half with one from the second half, the following conditions are required:

1. The first half alone forms an independent set
2. The second half alone forms an independent set
3. There are no edges between first-half vertices and second-half vertices (cross edge constraint)

To efficiently handle condition 3, for each independent set in the first half, we compute a “blocked mask” indicating which second-half vertices become unavailable, and check consistency with the second-half independent set.

Combining via Blocked Mask

• Selecting an independent set from the first half blocks some second-half vertices due to edges crossing from first-half vertices to the second half. We represent this as a blocked mask (bitmask).
• For a selected second-half vertex set \(s_2\), we need \(\text{blocked} \cap s_2 = \emptyset\) (i.e., blocked is a subset of the complement of \(s_2\)).
• For each second-half independent set \(s_2\), we need to efficiently find the maximum first-half weight among all subsets of \(\overline{s_2}\) (the complement of \(s_2\)).

This can be preprocessed using SOS (Sum/Max over Subsets) DP.

Algorithm

Step 1: Enumerate the First Half

Split the vertices into the first half (\(0, 1, \ldots, \lfloor N/2 \rfloor - 1\)) and the second half (\(\lfloor N/2 \rfloor, \ldots, N-1\)).

Enumerate all \(2^{\lfloor N/2 \rfloor}\) subsets of the first half, and for those that are independent sets: - Compute the weight sum \(w_1\) - Compute the blocked mask \(b\) for the second half (OR of edges from selected first-half vertices to the second half) - Update \(\text{best\_first}[b] = \max(\text{best\_first}[b],\, w_1)\)

Step 2: SOS DP (Subset Max)

Update \(\text{best\_first}[b]\) so that it contains “the maximum over all subsets of \(b\)”.

Specifically, for each bit \(j\): $\(\text{best\_first}[b] \leftarrow \max(\text{best\_first}[b],\, \text{best\_first}[b \oplus (1 \ll j)]) \quad (\text{if the } j\text{-th bit of } b \text{ is 1})\)$

After this, \(\text{best\_first}[s]\) represents “the maximum weight of a first-half independent set whose blocked mask is a subset of \(s\)”.

Step 3: Enumerate the Second Half and Combine

Enumerate all \(2^{\lceil N/2 \rceil}\) subsets of the second half, and for those that are independent sets: - Compute the weight sum \(w_2\) - Compute the available mask \(= \overline{s_2}\) (bits in the second half not included in \(s_2\)) - Look up \(\text{best\_first}[\text{available}]\) (this gives the maximum first-half weight \(w_1\) satisfying the constraints) - Update \(\text{ans} = \max(\text{ans},\, \min(w_1 + w_2,\, M))\)

Concrete Example

For \(N = 4,\, M = 100,\, P = [30, 40, 50, 20]\) with only the edge \((1,2)\):

• First half: vertices \(\{0, 1\}\), second half: vertices \(\{2, 3\}\)
• Edge \((0, 1)\) is within the first half, so only \(\{0\}\), \(\{1\}\), or \(\emptyset\) are independent sets in the first half
• Combine with each second-half independent set, choosing the one with the maximum total that does not exceed \(M\)

Complexity

Let \(h_1 = \lfloor N/2 \rfloor,\; h_2 = \lceil N/2 \rceil\) (both at most 20).

• Time complexity: \(O(2^{h_1} \cdot h_1 + 2^{h_2} \cdot h_2 + 2^{h_2} \cdot h_2)\)
  • First half enumeration: \(O(2^{h_1} \cdot h_1)\)
  • SOS DP: \(O(2^{h_2} \cdot h_2)\)
  • Second half enumeration + combining: \(O(2^{h_2} \cdot h_2)\)
  • Overall: approximately \(O(N \cdot 2^{N/2})\)
• Space complexity: \(O(2^{h_2})\) (for the \(\text{best\_first}\) table)

When \(N = 40\), \(2^{20} \approx 10^6\), which is sufficiently fast.

Implementation Notes

• Bitmask management of adjacency: By storing the adjacent vertices of each vertex \(i\) as a bitmask adj[i], we can quickly check independent set conditions using mask & adj[i].

• Speeding up independent set checking: When adding each vertex, we only check adjacency with already selected vertices with smaller indices, avoiding redundant checks (adj[i] & ((1 << i) - 1) & mask).

• Direction of SOS DP: Since we want “max over subsets”, we propagate from set bits to unset bits. This allows \(O(1)\) maximum value retrieval at query time.

• Upper bound constraint of \(M\): Don’t forget to take min(total, M) to ensure the total does not exceed \(M\).

  Source Code

import sys
from itertools import combinations

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    P = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
    
    # adjacency as bitmask
    adj = [0] * N
    for _ in range(K):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        adj[u] |= (1 << v)
        adj[v] |= (1 << u)
    
    # Maximum weight independent set with N <= 40
    # Use meet-in-the-middle approach
    
    if N <= 20:
        # Simple bitmask enumeration
        best = 0
        for mask in range(1 << N):
            # Check if independent set
            valid = True
            total = 0
            for i in range(N):
                if mask & (1 << i):
                    if mask & adj[i]:
                        valid = False
                        break
                    total += P[i]
            if valid:
                best = max(best, min(total, M))
        print(best)
        return
    
    # Meet in the middle for N <= 40
    # Split into two halves
    half1 = N // 2
    half2 = N - half1
    
    # For each subset of the first half that is independent,
    # record which vertices in the second half are still available
    # and the total weight
    
    # Enumerate all independent sets in the first half
    # For each, compute: weight and "blocked" mask in second half
    
    # First half: vertices 0..half1-1
    # Second half: vertices half1..N-1
    
    # For second half, adj restricted to second half vertices
    # adj2[i] for i in second half = adj[half1+i] restricted to second half bits
    
    # We need to group first-half results by the "available mask" in the second half
    # Then for each group, we want the maximum weight from first half
    # Then enumerate independent sets in available vertices of second half
    
    # But the number of distinct "available masks" could be up to 2^half2 which is 2^20 = 1M
    # And for each we enumerate subsets... that's too much directly
    
    # Alternative: enumerate both halves independently, then combine
    
    # For first half: enumerate all independent sets, store (blocked_mask_in_half2, weight)
    # For second half: enumerate all independent sets, store (mask_in_half2, weight)
    # Combine: for each second half IS with mask s2, we need first half IS whose blocked_mask & s2 == 0
    # blocked_mask = union of adj[i] & half2_bits for i in first half IS
    
    # Group first half by blocked_mask, keep max weight for each blocked_mask
    # Then for each second half IS (s2, w2), iterate over all blocked_masks that are subsets of complement of s2
    # Use SOS (sum over subsets) - actually we need max over subsets
    
    # We'll use "max over supersets" DP
    # For first half: best_first[blocked] = max weight of first half IS with that blocked mask
    # Then do a "superset max" relaxation: for each blocked mask b, 
    #   best_first[b] = max over all b' where b' is superset of b of best_first[b']
    # Wait, we want: given available = complement of s2, find max best_first[b] where b is subset of available_complement... 
    # Actually: we need blocked & s2 == 0, i.e., blocked is subset of ~s2
    # So for a given s2, we want max of best_first[b] over b subset of (~s2 & half2_fullmask)
    # This is "max over subsets" which can be done with SOS in O(2^half2 * half2)
    
    h2_full = (1 << half2) - 1
    
    best_first = [-1] * (1 << half2)
    
    for mask in range(1 << half1):
        valid = True
        total = 0
        blocked = 0
        bits = mask
        while bits:
            i = (bits & -bits).bit_length() - 1
            if mask & adj[i] & ((1 << half1) - 1) & ((1 << (i)) - 1):  # check lower bits only to avoid double
                valid = False
                break
            total += P[i]
            blocked |= (adj[i] >> half1) & h2_full
            bits &= bits - 1
        if not valid:
            continue
        if total > best_first[blocked]:
            best_first[blocked] = total
    
    # SOS max over subsets: best_first[b] = max over all b' subset of b
    # We want for query s: max best_first[b] for b subset of s
    # Standard SOS: iterate bits, for each bit, propagate from subset to superset
    for bit in range(half2):
        for b in range(1 << half2):
            if b & (1 << bit):
                sub = b ^ (1 << bit)
                if best_first[sub] > best_first[b]:
                    best_first[b] = best_first[sub]
    
    ans = 0
    for mask2 in range(1 << half2):
        valid = True
        total2 = 0
        for j in range(half2):
            if mask2 & (1 << j):
                real_j = half1 + j
                local_adj = (adj[real_j] >> half1) & h2_full
                if mask2 & local_adj & ((1 << j) - 1):
                    valid = False
                    break
                total2 += P[real_j]
        if not valid:
            continue
        avail = h2_full ^ mask2  # bits not in mask2 (but we need complement of mask2 for blocked constraint)
        # We need blocked subset of ~mask2 in half2 bits = avail
        w1 = best_first[avail]
        if w1 < 0:
            continue
        val = min(total2 + w1, M)
        if val > ans:
            ans = val
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.