Overview

Given \(N\) research themes with prerequisite relations (if you choose \(U_j\), you must also choose \(V_j\)), select a subset that satisfies all prerequisites and maximizes the total profit (value \(P_i\) minus cost \(C_i\)). Since the constraint \(N \le 15\) is small, we can solve this using brute-force enumeration over all subsets (bit enumeration).

Discussion

This problem is generally known as the “maximum weight closure problem” (also known as the “burn or bury” problem), and can also be solved using maximum flow (minimum cut) algorithms. However, in this problem the constraint \(N \le 15\) is set to a very small value.

The total number of “choose or not choose” combinations for research themes is \(2^N\), which is at most \(2^{15} = 32{,}768\) when \(N=15\). Therefore, we can solve this well within the time limit by exhaustively checking all possible selections, without needing any advanced algorithms.

If we naively manage and check sets using arrays or lists, the constant factor in execution time may become large. However, by leveraging “bit operations” that represent sets as integer bit strings, we can perform prerequisite checks and profit calculations very efficiently.

Algorithm

1. Profit Calculation: Precompute the net profit of choosing each theme \(i\) as \(W_i = P_i - C_i\).

2. Bit Representation of Prerequisites: Manage the set of themes required when choosing theme \(i\) as an integer (bitmask) req[i]. For example, if theme \(0\) requires themes \(1\) and \(2\), then set bit \(1\) and bit \(2\) of req[0] (in binary: ...0110).

3. Precomputation of Subset Profits: For all possible selections (mask) from \(0\) to \(2^N - 1\), compute the total profit of the selected themes and store it in the array profit_sum.

4. Condition Checking and Maximum Value Update: For every mask, check whether all prerequisite relations are satisfied.

   • For every theme \(i\) included in mask, if mask & req[i] == req[i] holds, then all prerequisite themes for \(i\) are included in mask.
   • Among all mask values that satisfy the conditions, find the maximum total profit. Since the profit of selecting nothing (mask = 0) is \(0\), initialize the maximum value to \(0\).

Complexity

• Time complexity: \(O(N 2^N)\) There are \(2^N\) total subsets, and checking whether each subset satisfies the prerequisites takes \(O(N)\) time. When \(N=15\), this amounts to approximately \(15 \times 32{,}768 \approx 5 \times 10^5\) operations, which comfortably fits within the typical time limit of 2 seconds.
• Space complexity: \(O(2^N)\) This is for the array profit_sum that stores the total profit of each subset, holding \(2^N\) elements. For \(N=15\), this is \(32{,}768\) elements, which poses absolutely no problem for memory limits.

Implementation Notes

• Set Operations via Bit Manipulation: Whether theme \(i\) is included in mask can be checked with mask & (1 << i). Also, checking whether all required themes are included with (mask & req[i]) == req[i] is a concise and fast expression unique to bit operations.

• Fast Precomputation Using LSB (Least Significant Bit): When computing profit_sum, we can extract only the rightmost 1 bit in mask using lsb = mask & -mask. By leveraging this, we can compute profit_sum[mask] = profit_sum[mask ^ lsb] + profits[i] in a recurrence-like fashion, performing the profit calculation for each mask in \(O(1)\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    profits = []
    idx = 2
    for _ in range(N):
        P = int(input_data[idx])
        C = int(input_data[idx+1])
        profits.append(P - C)
        idx += 2
        
    req = [0] * N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        req[u] |= (1 << v)
        idx += 2
        
    profit_sum = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        profit_sum[mask] = profit_sum[mask ^ lsb] + profits[i]
        
    max_profit = 0
    for mask in range(1 << N):
        valid = True
        for i in range(N):
            if (mask & (1 << i)) and ((mask & req[i]) != req[i]):
                valid = False
                break
        if valid:
            if profit_sum[mask] > max_profit:
                max_profit = profit_sum[mask]
                
    print(max_profit)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.